[LEETCODE] 38: Count and Say(Python)

Count and Say - LeetCode

문제 설명

countAndSay(1)이 “1”일 때, countAndSay(n)는 countAndSay(n-1)에서 각 연속되는 숫자의 개수를 세 나열한 문자열이다. 즉 countAndSay(2)는 “11” ← 1개의 1, countAndSay(3)은 “21” ← 2개의 1, countAndSay(3)은 “1211” ← 1개의 2, 1개의 1… 이런 식이다. n이 주어졌을 때 countAndSay(n)을 구해보자.

나의 풀이

class Solution:
    def countAndSay(self, n: int) -> str:
        if n==1:
            return "1"
        say=self.countAndSay(n-1)
        answer=""
        key=say[0]
        count=1 # 현재까지의 key 개수
        for i in range(1,len(say)):
            if key==say[i]:
                count+=1
            else:
                answer+=str(count)
                answer+=key
                key=say[i]
                count=1
        answer+=str(count)
        answer+=key
        
        return answer

처음에는 단순 for문을 사용해 풀었다가 재귀를 사용한 것이 시간이 빠르길래 수정했다. n=1일 때까지 재귀를 돌리고, 각 원소별 중복되는 key 개수를 세면서 작성하면 된다.

시간복잡도

어차피 n부터 1까지 가기 때문에 for문과 동일하게 O(n*len(단계별 answer))이다.