38. Count and Say

LONGNEW·2023년 7월 31일
0

CP

목록 보기
135/155

https://leetcode.com/problems/count-and-say/?envType=featured-list&envId=top-google-questions

input :

  • n

output :

  • 재귀적 수행을 이루어 나온 숫자를 읽은 것을 출력하시오.

조건 :

  • countAndSay(1) = "1"
  • countAndSay(n)은 countAndSay(n - 1)의 결과를 읽는 것이다.
  • countAndSay(2)의 결과는 countAndSay(1)의 결과인 "1"을 읽는 것으로 1이 1개 있다는 의미로 "11"을 리턴한다. "{개수}{숫자}"의 형태를 보인다.

Solution explain : Solution1

idea

  • 주어진 조건에 맞는 재귀 함수를 제작한다.
  • base case : if n == 1: return f"1"
  • recursive case : 결과로 얻은 return값에 대한 순회를 수행한다.
  • prev, cnt 변수를 이용해 cnt > 0이상인 경우에만 "{개수}{숫자}"의 형태를 만족하도록 "{prev}{cnt}"를 ret변수에 더해준다.
  • 반복문이 끝나고 남은 값들도 넣어줘야 하니 이를 잊지 말자.

주의

  • 클래스 내부의 재귀 함수를 사용하는 경우 self 키워드를 꼭 사용해야 한다.
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return f"1"
        
        ret = ""
        temp = self.countAndSay(n - 1)
        prev, cnt = "", 0
        for item in temp:
            if prev != item and cnt > 0:
                ret += f"{cnt}{prev}"
                cnt = 0

            prev = item
            cnt += 1
            
        ret += f"{cnt}{prev}"
        return ret

0개의 댓글