LeetCode 38

도토코·2025년 4월 24일

알고리즘 문제 풀이

목록 보기

40/44

문제

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"
countAndSay(n) is the run-length encoding of countAndSay(n - 1).
Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511".

Given a positive integer n, return the nth element of the count-and-say sequence.

번역

문제 설명 (한국어)
Count‑and‑Say 수열은 다음과 같이 재귀적으로 정의된 숫자 문자열 수열입니다.

countAndSay(1) = "1"

countAndSay(n) 은 countAndSay(n - 1)에 런‑길이 인코딩(Run‑Length Encoding, RLE) 을 적용한 결과입니다.

런‑길이 인코딩(RLE) 은 연속해서 2번 이상 반복되는 동일한 문자를
문자 + 반복 횟수 로 치환하여 문자열을 압축하는 방법입니다.

예를 들어, 문자열 "3322251"을 압축할 때:

"33" → "23" (문자 3이 2번)

"222" → "32" (문자 2가 3번)

"5"  → "15" (문자 5가 1번)

"1"  → "11" (문자 1이 1번)

따라서 압축 결과는 "23321511"이 됩니다.

예시

1. 입력: n = 4

출력: "1211"

과정:
countAndSay(1) = "1"
countAndSay(2) = RLE("1") = "11"
countAndSay(3) = RLE("11") = "21"
countAndSay(4) = RLE("21") = "1211"

2. 입력: n = 1

출력: "1"

설명: 기본(base) 케이스입니다.

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"

        prev = "1" 
        
        for _ in range(2, n + 1):
            parts = []
            cnt = 1 
            
            for i in range(1, len(prev)):
                if prev[i] == prev[i-1]:
                    cnt += 1
                else:
                    parts.append(str(cnt))
                    parts.append(prev[i-1])
                    cnt = 1
                    
            parts.append(str(cnt))
            parts.append(prev[-1])
            prev = "".join(parts)
        return prev

상세 흐름

1. 베이스 케이스

n == 1일 때는 재귀나 반복 없이 바로"1" 반환한다.

2. 반복 준비

prev에 바로 직전 단계 문자열을 보관한다.
초기값은 "1"(즉, countAndSay(1)).

3. 각 단계별 변환

**for _ in range(2, n + 1)**
- 2번째 항부터 n번째 항까지 생성한다는 뜻이다.
런‑길이 인코딩(RLE) 과정

cnt를 1로 두고, prev를 인덱스 1부터 끝까지 탐색한다.
같은 글자가 이어지는 동안 cnt를 증가한다.
다른 글자가 나오면 앞선 run이 끝난 것이므로
- parts.append(str(cnt))  횟수
- parts.append(prev[i-1]) 문자
- 카운터를 1로 초기화해 새 run 시작한다.

마지막 run 처리
- for 루프가 종료되면 맨 끝 run은 아직 parts에 안 들어가 있으므로 한 번 더 append.
문자열 결합
- parts 리스트: ['2','1','1','3', ...] 처럼 토큰 단위로 저장되어 있다.
- "".join(parts)로 모든 토큰을 한 번에 이어 붙여 새 문자열 prev 완성된다.
- 이 과정이 끝나면 prev는 countAndSay(k) (k는 현재 반복 인덱스) 값이 된다.