HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
Count and Say

Count and Say

문제

38. Count and Say
Medium
948
2722
Add to List
Share
The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
  • countAndSay(1) = "1"
  • countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.
To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
For example, the saying and conversion for digit string "3322251":
notion image
Given a positive integer n, return the nth term of the count-and-say sequence.
Example 1:
Example 2:
Constraints:
  • 1 <= n <= 30

풀이

은찬
 
현석
재영
string메서드가 익숙치 않아서인지, 그닥 와닿지 않은 풀이긴 하네유...!
 
가영
희진
풀다가 막혀서 블로그좀 봤습니당...ㅎ
효성

실패..

참고한 풀이

Link
https://leetcode.com/problems/count-and-say/
Deadline
Nov 16, 2021
Status
Archived
Type
string
Input: n = 1
Output: "1"
Explanation: This is the base case.

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

/**
 * @param {number} n
 * @return {string}
 */
const countAndSay = (n) => {
    let answer = "1";
    
    for(let i = 2; i <= n; i++){
        let count = 1;
        let before = answer[0];
        let string = "";
        
        for(let j = 1; j < answer.length; j++){
            if(answer[j] === before){
                count++;
            } else{
                string += `${count}${before}`;
                count = 1;
                before = answer[j];
            }
        }
        
        answer = `${string}${count}${before}`;
    }
    
    return answer;
};
const countAndSay = function(n) {
  if (n === 1) return '1'
  if (n === 2) return '11'
  
  let currCAS = ''
  let length = 1
  const prevCAS = countAndSay(n-1)
  let num = prevCAS[0]
  console.log(prevCAS)
  
  for (let i = 1; i < prevCAS.length; i++) {
    let currNum  = prevCAS[i]
    if (currNum === num) {
      length ++;
    } else {
      currCAS += `${length}${num}`
      num = currNum
      length = 1;
    }
    if(i === prevCAS.length -1) {
      currCAS += `${length}${num}` 
    }
  }
  return currCAS
};
const updateResult = (result, prevNumsLength, prev) => {
  return `${result}${prevNumsLength}${prev}`;
};
const isLastIndex = (i, length) => i === length - 1;

const countAndSay = (n) => {
  if (n === 1) return "1";

  let result = "";

  let prevResult = countAndSay(n - 1);

  let prevResultLength = prevResult.length;
  let prevNums = [];

  for (let i = 0; i < prevResultLength; i += 1) {
    const now = prevResult[i];
    if (prevNums.length && prevNums[0] !== now) {
      result = updateResult(result, prevNums.length, prevNums[0]);
      prevNums = [];
    }
    prevNums.push(now);
    if (isLastIndex(i, prevResult.length) && prevNums.length) {
      result = updateResult(result, prevNums.length, prevNums[0]);
    }
  }
  return result;
};

// faster than 91%
const countAndSay = n => {
    let digitString = '1';    
    
    for (let i = 1; i < n; i++) {
        const numbers = [];
        
        digitString.split('').forEach((value, index) => {
            if (numbers[numbers.length - 1]?.charAt() !== value) {
                numbers.push(value);
            } else {
                numbers[numbers.length - 1] += value;
            }
        });
        
        digitString = numbers.map(value => value.length + value.charAt()).join('');
    }
    
    return digitString;
};
var countAndSay = function(n) {
    let answer = '1'
    if(n === 1) {
        return answer
    }else{
        
        for(let i=2;i<=n;i++){
            let count = 1;
            let latest = answer[0]
            let localAnswer = ''
            for(let j=1;j<answer.length;j++){
                if(latest === answer[j]){
                    count++;
                }else{
                    localAnswer += `${count}${latest}`
                    count = 1
                    latest = answer[j]
                }
                
            }
            
            answer = `${localAnswer}${count}${latest}`
        }
        return answer
    }
    
};
var countAndSay = function(n) {
    if(n === 1) {
        return '1';
    }
    let result = ''
    const recursive = (str) => {
        result = '';
        let last = '';
        let cnt = 1;
        let char = str[0];
        for(let j=0; j<str.length-1; j++) {
            if(str[j] === str[j+1]) {
                cnt++;
            }
            else {
                last = '1'+ str[str.length -1];
            }
        }
        result += cnt + char + last;
        n--;
        if(n === 2) {
            return result.trim();
        }
        recursive(result);
    }
    recursive('11');
    return result;
};
var countAndSay = function(n) {
    let str = '1';
    for(let i=1; i<n; i++) {
        let splitedArr = str.split('');
        str = '';
        let cnt = 1;
        for(let j=0; j<splitedArr.length; j++) {
            if(splitedArr[j] !== splitedArr[j+1]) {
                str += cnt + splitedArr[j];
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
    }
    return str;
};