38. Count and Say

https://leetcode.com/problems/count-and-say

Count and Say - LeetCode

 

이 문제는 한국에서는 베르나르 베르베르의 소설 '개미'에 등장하여 흔히 **"개미 수열"**이라고도 불리는 Count-and-Say (읽고 말하기) 수열 문제입니다.

반복적인 방법(Iterative)을 사용한 논리와 파이썬 풀이를 단계별로 설명해 드리겠습니다.

1. 논리 구조 (Logic Breakdown)

이 문제의 핵심은 이전 단계의 문자열을 소리 내어 읽는 것입니다. 이를 **런 렝스 부호화(Run-Length Encoding)**라고도 합니다.

문자열을 왼쪽에서 오른쪽으로 훑으며, 연속된 동일한 숫자를 그룹으로 묶습니다. 각 그룹에 대해 다음 두 가지 정보를 결합합니다:

1. 개수 (Count): 연속된 숫자가 몇 개인지
2. 숫자 (Digit): 그 숫자가 무엇인지

예시 (n=4일 때):

• n=1: "1" (기본값)
• n=2: 이전 값 "1"을 읽습니다. → 1이 1개 → "11"
• n=3: 이전 값 "11"을 읽습니다. → 1이 2개 → "21"
• n=4: 이전 값 "21"을 읽습니다.
  • 첫 번째 그룹: '2'가 1개 → "12"
  • 두 번째 그룹: '1'이 1개 → "11"
  • 결과 합치기: "1211"

---

2. 파이썬 반복 풀이 (Iterative Solution)

재귀(Recursion)를 사용하지 않고 반복문으로 처리하면 스택 오버플로우를 방지하고 메모리를 더 효율적으로 사용할 수 있습니다.

Python

class Solution:
    def countAndSay(self, n: int) -> str:
        # 기본 케이스 처리
        if n == 1:
            return "1"
        
        # 첫 번째 수열 시작
        current_s = "1"
        
        # 2부터 n까지 반복하며 다음 수열 생성
        for _ in range(2, n + 1):
            next_s = []
            i = 0
            length = len(current_s)
            
            while i < length:
                count = 1
                # 현재 위치(i)의 문자와 다음 문자가 같으면 count 증가
                while i + 1 < length and current_s[i] == current_s[i+1]:
                    i += 1
                    count += 1
                
                # '개수'와 '숫자'를 리스트에 추가
                next_s.append(str(count))
                next_s.append(current_s[i])
                
                # 다음 새로운 숫자로 이동
                i += 1
            
            # 리스트를 문자열로 합쳐서 current_s 갱신
            current_s = "".join(next_s)
            
        return current_s

3. 코드 상세 설명

1. 기본 케이스 (Base Case): n=1이면 단순히 "1"을 반환합니다.
2. 외부 루프 (Outer Loop): 2번째 수열부터 n번째 수열까지 차례대로 생성합니다.
3. 내부 로직 (Grouping):
   • while 루프를 통해 현재 문자열 current_s를 처음부터 끝까지 스캔합니다.
   • 내부의 while 루프(current_s[i] == current_s[i+1])는 연속된 숫자가 끝날 때까지 인덱스를 이동시키며 count를 셉니다.
   • 연속된 구간이 끝나면 count(개수)와 current_s[i](해당 숫자)를 next_s 리스트에 추가합니다.
4. 갱신 (Update): 만들어진 next_s 리스트를 문자열로 변환하여 current_s에 저장하고 다음 단계로 넘어갑니다.

4. 복잡도 분석

• 시간 복잡도: O(M)
  • 여기서 M은 생성되는 수열의 전체 길이입니다. 이 수열은 단계가 지날수록 길이가 급격히 늘어납니다(약 1.3배씩 증가). n=30 정도의 제약 조건에서는 충분히 빠르게 동작합니다.
• 공간 복잡도: O(L)
  • L은 생성된 문자열의 최대 길이입니다. 이전 문자열과 새로운 문자열을 저장할 공간이 필요합니다.