[LeetCode] 38. Count and Say (python)

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

Count and Say - LeetCode

---

📍 Problem

count-and-say sequence는 재귀적으로 정의된 숫자 문자열로,

- countAndSay(1) = '1' 로 시작해서, 

- countAndSay(n) 은  countAndSay(n-1) 를 읽은 문자열을 숫자로 표현한다.

 

예를 들어

Input n=2 인 경우, 

countAndSay(2) 는 countAndSay(1)의 결과값 '1' 의 숫자들을 count해 문장으로 만든 결과값이다.

-> '1개의 1' 만 있으므로 countAndSay(2) = '11' 이 된다.

 

n=3인 경우,

countAndSay(2) = '11' 를 '2개의 1' 로 읽어 결과가 '21' 이 된다.

 

* 주의할 점은 숫자 count는 같은 숫자가 연속적으로 이어질 때까지만 유효하다. 

 

위와 같은 방식으로 countAndSay(n-1)  = '111221' 인 경우,

countAndSay(n)은 '3개의 1, 2개의 2, 1개의 1' 로, '312211' 가 된다. 

---

💡 Solution

n번째 countAndSay 값을 구하려면 n-1의 countAndSay 값이 필요하다.

숫자 문자열을 count하고 읽는 함수 (readString())를 구현하고, 이를 n-1 번 반복하는 형식으로 구현하였다.

 

readString() 함수의 경우 앞선 문자(prev)와 현재 문자를 비교하여 동일한 경우 갯수(cnt)를 업데이트하고, 

다른 경우 결과 string (res)에 지금까지 count한 문자와 갯수를 저장한다. 

 

class Solution(object):
    def countAndSay(self, n: int) -> str:
        say = '1' # n: 1 -> say: '1'

        # 이전 say값을 읽어 n번째 say값을 구한다. 
        # (이미 1에 대한 say 값은 구해진 상태이므로 n-1번 반복)
        for i in range(1, n):
            say = self.readString(say)

        return say

    def readString(self, seq: str) -> str:
        res = ''
        prev = '' 
        cnt = 0
        for i in range(len(seq) + 1):

            # 첫 문자의 경우 prev 문자를 첫 문자로 저장하고 넘어간다.
            if i == 0:
                prev = seq[i]
                cnt += 1

            # string이 끝나면 현재 prev 문자와 cnt를 결과에 업데이트하고 끝낸다. 
            elif i == len(seq):
                res += (str(cnt) + prev)
            
            # 문자가 이전 문자와 같은 경우, cnt를 추가하고
            # 다를 경우 res를 업데이트 하고 prev와 cnt를 초기화한다. 
            else:
                if prev == seq[i]:
                    cnt += 1
                else:
                    res += (str(cnt) + prev)
                    prev = seq[i]
                    cnt =  1
        return res