LeetCode 38(Count and Say, Python)

1. 문제 링크

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

Count and Say - LeetCode

2. 문제 설명

• count-and-say sequence는 재귀적인 공식에 의해 정의된 숫자 문자열 시퀀스를 의미
• countAndSay(1) = "1"로 default값을 셋팅한 후,
  • countAndSay(n)의 경우, countAndSay(n-1)에서 해당 숫자를 몇번 말했는지 + 해당 숫자 + 를 sequence로 표현 
• 3322251의 경우 → 2번의 3, 3번의 2, 1번의 5, 1번의 1이므로 → 23321511을 반환 
• 예시) n=4 라면
  • countAndSay(1) = "1" 
  • countAndSay(2)은 1번의 1이 등장했으므로 "11"
  • countAndSay(3)은 2번의 1이 등장했으므로 "21"
  • countAndSay(4)는 1번의 2와 1번의 1이 등장했으므로 "1211" 이 되어, "1211"를 반환한다. 

3. 처음 풀이

• 오랜만에 한번의 코드로 submission 통과했다 :) 
  • 먼저 n=1 일때 return = "1" 을 하였고, 
  • 1이 아닌 n에 대해서는, n-1의 countAndSay값을 불러온 후,
    • 해당 string에 대해 for문을 돌려서, sequence를 변환하는 작업을 진행
      • default로 count=1, nums=-1로 셋팅한 후,
        • string 값이 nums와 같다면 count를 1씩 높이고, 
        • 같지 않은데, nums가 -1이 아니라면(초기셋팅값), output에 str(count)+str(num)를 concat하여 반환

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"

        else:
            count = 1 
            num = -1
            output = ""
            for i in self.countAndSay(n-1):
                if i == num:
                    count += 1
                else:
                    if num != -1:
                        output += str(count)+str(num)
                    num = i
                    count = 1
            output += str(count)+str(num)
        
        return output

 

4. 다른 풀이

• 많은 풀이가 위의 풀이처럼 재귀를 사용하여 n-1값을 불러오는 구조로 코드를 짠 것 처럼 보였음
  • 아래 풀이는 n=1일 때부터 n=n일때까지 for문 돌린 케이스

class Solution:
    def countAndSay(self, n: int) -> str:
        curr = [1]
        for _ in range(n - 1):
            nxt = []
            cnt = 1
            for i in range(1, len(curr)):
                if curr[i] == curr[i - 1]:
                    cnt += 1
                else:
                    nxt.append(cnt);
                    nxt.append(curr[i - 1])
                    cnt = 1
            if curr:
                nxt.append(cnt); nxt.append(curr[-1])
            curr = nxt
        return "".join(map(str, curr))

 

• itertools library를 import해서, groupby 시킨 값을 concat한 풀이도 있었음 

from itertools import groupby

class Solution:
    def countAndSay(self, n: int) -> str:
        output = '1'
        for i in range(n-1):
            output = ''.join([str(len(list(g))) + k for k, g in groupby(output)])
        return output

 

5. 배운 점

• itertools의 groupby