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