파이썬으로 룩 앤 세이(Look-and-Say) 수열의 n번째 항 구하기

숫자 n이 주어졌을 때, '룩 앤 세이(Look and Say)' 수열의 n번째 항을 생성하는 문제입니다. 이 수열은 직전 항을 읽으면서 연속된 숫자의 개수를 함께 말하는 방식으로 만들어지며, 처음 몇 개의 항은 다음과 같습니다.

• 1
• 11
• 21
• 1211
• 111221

룩 앤 세이 수열의 읽는 방법

각 항은 바로 앞 항을 왼쪽부터 차례로 읽으며, 같은 숫자가 연속으로 나타나는 횟수를 세어 "개수 + 숫자" 형태로 표현합니다.

• 1 — 첫 번째 항은 "하나(1)"로 시작합니다.
• 11 — 이전 항 1을 읽어 "1이 하나"라고 말합니다.
• 21 — 이전 항 11을 읽어 "1이 둘"이라고 말합니다.
• 1211 — 이전 항 21을 읽어 "2가 하나, 1이 하나"라고 말합니다.
• 111221 — 이전 항 1211을 읽어 "1이 하나, 2가 하나, 1이 둘"이라고 말합니다.

문제 정의

n이 주어질 때(1 ≤ n ≤ 30), 룩 앤 세이 수열의 n번째 항을 문자열로 반환해야 합니다.

접근 방법

다음 단계에 따라 문제를 해결할 수 있습니다.

1. s := "1"로 초기화합니다.
2. n = 1이면 s를 그대로 반환합니다.
3. i를 2부터 n까지 반복하며 다음을 수행합니다.
   • j := 0, temp := 빈 문자열, curr := 빈 문자열, count := 0으로 초기화합니다.
   • j가 s의 길이보다 작은 동안 반복합니다.
     • curr이 빈 문자열이면 curr := s[j], count := 1로 설정하고 j를 1 증가시킵니다.
     • curr이 s[j]와 같으면 count와 j를 각각 1씩 증가시킵니다.
     • 그렇지 않으면 temp에 count(문자열 변환)와 curr을 이어 붙인 뒤, curr을 비우고 count를 0으로 초기화합니다.
   • while 루프가 끝나면 마지막으로 남은 그룹도 temp에 추가하고, s := temp로 갱신합니다.
4. 모든 반복이 끝나면 s를 반환합니다.

파이썬 구현 예제

아래 코드는 위 알고리즘을 그대로 구현한 것입니다. 각 자릿수를 한 번씩만 순회하면서 연속된 숫자의 개수를 세어 새로운 항을 만듭니다.

class Solution(object):
    def solve(self, n):
        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

ob = Solution()
n = 5
print(ob.solve(n))

입력

5

출력

"111221"

복잡도 분석

매 단계마다 이전 항의 모든 문자를 한 번씩 확인하므로, 시간 복잡도는 O(n × L)입니다. 여기서 L은 n번째 항의 길이입니다. 룩 앤 세이 수열의 항 길이는 콘웨이 상수(약 1.3036)의 비율로 증가하지만, n ≤ 30 범위에서는 매우 빠르게 동작합니다.