[Python/파이썬] LeetCode 38번 Count and Say

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

코드

def countAndSay(n):
    string = "1"
    for _ in range(n-1):
        new_string = ""
        cnt = 1
        prev = string[0]
        for s in string[1:]:
            if s == prev:
                cnt += 1
            else:
                new_string += (str(cnt)+prev)
                prev = s
                cnt = 1
        new_string += (str(cnt)+prev)
        string = new_string
    return string

 

제한 조건을 보면 1 <= n <= 30으로 범위가 크지 않다. 이러면 시간 복잡도가 O(N^2)가 되더라도 연산은 900번이므로 이중반복문으로 구현하여 풀이할 수 있다.