[Leetcode] 38. Count and Say

재귀로 풀었는데 빠르다?

문제 설명 - Count and Say

Count-and-Say 수열은 숫자 문자열로 이루어진 수열이다.
이 수열은 다음과 같은 재귀적 정의를 따른다:

• countAndSay(1) = "1" (기본 케이스)
• countAndSay(n)은 countAndSay(n-1)의 런-렝스 인코딩(Run-Length Encoding) 결과로 정의된다.

 

런-렝스 인코딩이란?

연속해서 같은 문자가 나올 경우, 그 문자의 개수와 문자를 이어붙이는 방식이다.
예를 들어, 문자열 "3322251"에 대해,

• "33" → "23"
• "222" → "32"
• "5" → "15"
• "1" → "11"

결과적으로 "23321511"이 된다.

 

조건 정리

• 1 ≤ n ≤ 30
• 문제는 메모리나 성능에 크게 부담이 없으므로 단순 반복(iterative)으로 풀 수 있다.

 

풀이 전략

이 문제는 수열을 한 단계씩 만들어가는 방식으로 접근하면 된다.
즉, countAndSay(1)부터 시작해서, n번째까지 반복적으로 결과를 생성하는 것이다.

구체적인 과정은 다음과 같다:

1. 시작 문자열을 "1"로 초기화한다.
2. 2부터 n까지 차례대로 다음 문자열을 만들어간다.
3. 현재 문자열을 왼쪽부터 읽으며, 같은 숫자가 반복되는 구간을 찾는다.
4. 개수와 숫자를 기록하여 새로운 문자열로 만든다.
5. 이 과정을 n번 반복하면 최종 문자열이 나온다.

이 문제를 그냥 해석해서 재귀로 구현하면 아래와 같이 간단히 풀 수 있다.

 

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        
        cnt = 0
        num = ""
        ans = ""
        for ch in self.countAndSay(n - 1):
            if num == "":
                num = ch
                cnt += 1
                continue
            
            if num != ch:
                ans += str(cnt) + num
                num = ch
                cnt = 1
            else:
                cnt += 1
        
        return ans + str(cnt) + num

 

추가 고려 사항

문제에서 Follow-up으로 반복적(iterative) 풀이를 요청하고 있다.
재귀(recursive)로도 풀 수 있지만, 반복문을 이용할 수도 있는가보다.

메모리 사용량을 줄이고 더 효율적인 코드를 작성할 수 있다는데, 혹시 푸신 분은 댓글에 링크를😁