여기에서 Count and Say 시퀀스를 볼 수 있습니다. 이것은 몇 개의 항이 아래와 같은 시퀀스입니다 -
- 1
- 11
- 21
- 1211
- 111221
문자열은 다음과 같이 읽힙니다.
- 1(하나)
- 11 (One 1) 그래서 앞의 1을 읽고 "One 1"이라고 말하세요
- 21 (Two 1) 그래서 앞의 11을 읽고 "Two 1"이라고 말하세요
- 1211 (One 2 One 1) 그래서 앞의 21을 읽고 "One 2 one 1"이라고 말하세요.
- 111221 (하나 1 하나 2 둘 1) 그래서 앞의 1211을 읽고 "하나 1 하나 2 둘 1"이라고 말하세요
숫자 n, 1 <=n <=30이 있다고 가정하면 n번째 항을 생성해야 합니다.
이를 해결하기 위해 우리는 다음과 같은 접근 방식을 따를 것입니다 -
- set s :="1"
- n =1이면 s를 반환합니다.
- i에 대해 :=2 ~ n + 1
- j :=0, temp :="", curr ="" 및 count :=0
- j
- curr이 ""이면 curr :=s[j], count :=1이고 j를 1만큼 증가
- curr이 s[j]이면 count와 j를 1만큼 늘립니다.
- 그렇지 않으면 temp :=temp + 문자열로 계산 + curr, curr ="", count :=0
- temp :=temp + 문자열로 계산 + curr
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object): def countAndSay(self, n): """ :type n: int :rtype: str """ s = "1" if n == 1: return s for i in range(2,n+1): j = 0 temp = "" curr = "" count = 0 while j<len(s): #print(curr,count) if curr =="": #print(curr) curr=s[j] count=1 j+=1 elif curr == s[j]: #print(curr) count+=1 j+=1 else: #print(count,curr) temp+= str(count) + curr curr="" count = 0 #print(temp) temp+=str(count) + curr s=temp return s ob1 = Solution() print(ob1.countAndSay(6))
입력
print(ob1.countAndSay(6))
출력
312211