38. Count and Say

문제

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

countAndSay(1) = "1"

countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you "say" a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

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

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

접근

#재귀

재귀 알고리즘을 사용한다. countAndSay(n-1)의 결과값을 불러와, 그 문자열을 for루프로 돌며 주어진 조건에 맞는 문자열을 만든다. 이 과정에서 갯수를 카운트하는 ct변수를 사용한다. for루프가 종료되면, 그 값을 리턴시킨다. n==1일때는 초기값으로, 무조건 1을 리턴한다.

파이썬에서는 재귀 호출을 하기 위해 self.함수명을 사용한다.

코드

class Solution:
    def countAndSay(self, n: int) -> str:
        res = ""
        ct = 1 # 갯수 카운트
        
        if n == 1:
            return "1"
        
        prev =  self.countAndSay(n - 1) # 재귀
        
        for i in range(len(prev)):
            if  i == len(prev) - 1 or prev[i] != prev[i + 1]:
                res += str(ct) + prev[i]
                ct = 1
            else :
                ct +=1
                
        return res

효율성

Runtime: 57 ms, faster than 82.85% of Python3 online submissions for Count and Say.
Memory Usage: 13.9 MB, less than 86.43% of Python3 online submissions for Count and Say.