[LeetCode] 38. Count and Say

해당 문제의 설명이 매우 조악하다고 생각하기에 재설명하고자 한다.

n이 1일 경우 반환값은 "1"이라는 전제를 두고

실제로 사람이 읽는 것처럼 n에 대한 정보가 입력되는데 예시는 아래와 같다.

countAndSay(1) = "1"
// 이전 문자열 "1"을 읽었을 때 한개의 1 = "11"
countAndSay(2) = RLE of "1" = "11"
// 이전 문자열 "11"을 읽었을 때 두개의 1 = "21"
countAndSay(3) = RLE of "11" = "21"
// 이전 문자열 "21"을 읽었을 때 한개의 2 한개의 1 = "1211"
countAndSay(4) = RLE of "21" = "1211"

😎풀이

function countAndSay(n: number): string {
    // 기본 케이스: n이 1일 때는 "1"을 반환
    if (n === 1) return "1";
    
    // 이전 수열을 재귀적으로 계산
    const prevSequence = countAndSay(n - 1);
    
    let result = "";
    let count = 1;
  	// 첫 숫자 등록
    let currentDigit = prevSequence[0];
    
    // 이전 수열을 순회하면서 Run-Length Encoding 수행
    for (let i = 1; i < prevSequence.length; i++) {
        if (prevSequence[i] === currentDigit) {
            // 같은 숫자가 연속되면 카운트 증가
            count++;
        } else {
            // 다른 숫자를 만나면 지금까지의 카운트와 숫자를 결과에 추가
            result += count.toString() + currentDigit;
            currentDigit = prevSequence[i];
            count = 1;
        }
    }
    
    // 마지막 그룹 처리
    result += count.toString() + currentDigit;
    
    return result;
}