파이썬으로 Count and Say(세고 말하기) 수열 구현하기

Count and Say 수열이란?

Count and Say(세고 말하기) 수열은 이전 항을 소리 내어 읽는 방식으로 다음 항을 만들어 가는 흥미로운 수열입니다. 처음 몇 개의 항은 다음과 같습니다.

• 1
• 11
• 21
• 1211
• 111221

수열을 읽는 규칙

각 항은 바로 앞 항을 읽으면서 연속된 숫자의 개수와 그 숫자 자체를 차례로 말하는 방식으로 생성됩니다.

• 1 → "1" (하나의 1)
• 11 → 이전 항 "1"을 읽어 "1이 하나"라고 말합니다.
• 21 → 이전 항 "11"을 읽어 "1이 둘"이라고 말합니다.
• 1211 → 이전 항 "21"을 읽어 "2가 하나, 1이 하나"라고 말합니다.
• 111221 → 이전 항 "1211"을 읽어 "1이 하나, 2가 하나, 1이 둘"이라고 말합니다.

문제 정의

정수 n(1 ≤ n ≤ 30)이 주어졌을 때, Count and Say 수열의 n번째 항을 구하는 것이 목표입니다.

알고리즘 접근 방법

1. 문자열 s를 "1"로 초기화합니다.
2. n이 1이면 s를 그대로 반환합니다.
3. i를 2부터 n까지 반복하며 현재 문자열 s를 왼쪽부터 한 글자씩 훑습니다.
   • 현재 문자 curr이 비어 있으면 s[j]를 curr에 저장하고 count를 1로 설정한 뒤 j를 증가시킵니다.
   • curr이 s[j]와 같으면 count와 j를 각각 1씩 증가시켜 연속된 같은 숫자를 셉니다.
   • 다른 숫자가 나오면 지금까지 센 count와 curr을 결과 문자열 temp에 추가하고, curr과 count를 초기화합니다.
4. 내부 반복이 끝나면 남아 있는 count와 curr도 temp에 추가한 뒤, temp를 새로운 s로 사용합니다.
5. 모든 반복이 끝나면 s를 반환합니다.

이 방식은 문자열을 한 번씩만 훑기 때문에 각 단계마다 O(len(s))의 시간 복잡도로 처리할 수 있습니다.

파이썬 구현 예제

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        s = "1"
        if n == 1:
            return s
        for i in range(2, n + 1):
            j = 0
            temp = ""
            curr = ""
            count = 0
            while j < len(s):
                if curr == "":
                    curr = s[j]
                    count = 1
                    j += 1
                elif curr == s[j]:
                    count += 1
                    j += 1
                else:
                    temp += str(count) + curr
                    curr = ""
                    count = 0
            temp += str(count) + curr
            s = temp
        return s

ob1 = Solution()
print(ob1.countAndSay(6))

실행 결과 확인

입력:

ob1.countAndSay(6)

출력:

312211

5번째 항 "111221"을 읽으면 "1이 셋, 2가 둘, 1이 하나"이므로 6번째 항은 312211이 됩니다. 코드가 의도대로 동작하는 것을 확인할 수 있습니다.