2661 - 좋은수열
📌 문제
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
다음은 나쁜 수열의 예이다.
- 33
- 32121323
- 123123213
다음은 좋은 수열의 예이다.
- 2
- 32
- 32123
- 1232123
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.
📋 코드
import heapq
def check(string):
len_str = len(string)
for size in range(1, (len_str // 2) + 1):
first = 0
second = first + size
for step in range(len_str - 2 * size + 1):
if string[first + step:first + size + step] == string[second + step:second + size + step]:
return False
return True
N = int(input())
arr = ['1', '2', '3']
result = '1'
q = []
heapq.heappush(q, (-1, len(result)))
flag = False
while q:
length, now = heapq.heappop(q)
now_string = str(now)
for num in arr:
new_string = now_string + num
if check(new_string):
if len(new_string) == N:
print(int(new_string))
flag = True
break
heapq.heappush(q, (-len(new_string), int(new_string)))
if flag:
break💡 한마디
대부분 사람들이 재귀로 짰던데 워낙 재귀랑 친숙하지 않은 탓에 최대힙을 사용했다. 어려웠던 부분은 길이가 7에서 8로 넘어가는 부분인데,
- 길이 7 : 1213121
- 길이 8 : 12131231
길이 7에다가 1, 2, 3 중 하나를 더한다고 길이 8짜리 좋은 수열을 만들 수 없다. 그래서 길이 7에서 가능한 좋은 수열을 모두 힙에 넣은 뒤 가장 작은 수부터 뽑아 check 함수를 통해 검사했다.
