[파이썬/python] 백준 - 1469 숌 사이 수열

문제

https://www.acmicpc.net/problem/1469

---

문제 설명

1. 숌은 N개의 서로 다른 숫자로 구성되어 있는 집합 X이다.
2. 이를 통해 2N 길이의 숌 사이 수열 S를 만들어야 한다.
   1. X에 들어있는 모든 수는 숌 사이 수열 S에 두 번 등장해야 한다.
   2. X에 등장하는 수가 i라면 S에서 두 번 등장하는 i사이에는 i개의 수가 등장해야 한다.
3. 숌 사이 수열은 사전 순으로 가장 빠른 것을 출력하고, 없을 경우 -1을 출력한다.

 

---

풀이

첫번째 예제를 통해 문제를 이해해보자.

3
1 2 3

위와 같은 예제가 주어졌을 때

1 사이에는 1개의 숫자, 2 사이에는 2개, 3 사이에는 3개의 숫자가 들어가야 한다.

 

하나의 예시를 들어보면 2 3 1 2 1 3과 같다. 각 숫자 사이에는 숫자의 개수만큼의 수가 들어가 있다.

 

이 문제에서 X의 크기는 8보다 작거나 같은 자연수이다. 또한 X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수이다.

X의 크기가 매우 작기 때문에 모든 경우의 수를 전부 비교해도 시간복잡도가 충분할 것이라고 판단했다.

 

따라서 브루트포스, 백트래킹을 통해서 모든 경우의 수를 대입하고 모든 배열이 채워졌을 때 해당 배열을 출력했다.

이때 사전순으로 가장 빠른 것을 출력해야 하기 때문에 입력 배열을 오름차순으로 정렬한 후 낮은 수부터 순차적으로 배열에 삽입했다.

 

문제는 다음에는 어떤 원소를 탐색해야 하는가였다.

현재 원소를 배열에 2개 넣고 다음 원소를 어느 자리에 넣어야 하는지를 찾기 위해 while 문을 통해 현재 넣은 자리에서 1씩 증가하며 다음 넣을 위치를 판단했고, 원소를 방문처리하여 다음 원소를 넣을 때 중복 값이 들어가지 않도록 하였다.

 

최종적으로 재귀 함수에서 배열을 완성한다면 결과를 출력하고 exit() 함수를 통해 프로그램을 종료하도록 구현했다.

따라서 만약 재귀함수가 끝까지 돌아갔음에도 불구하고 프로그램이 종료되지 않았다면 결과를 도출하지 못했다는 것이기 때문에 -1을 출력했다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int,input().split())))
visited = [0 for _ in range(n)]
S = [-1 for _ in range(n*2)]


def recursion(s, depth):
    if depth == n:
        print(*S)
        exit()
    for i in range(n):
        if visited[i]:
            continue

        e = s + arr[i] + 1
        if e > 2*n-1:
            break

        if S[e] == -1 and S[s] == -1:
            S[e], S[s] = arr[i], arr[i]
            visited[i] = 1

            ns = s
            while ns < 2*n-1 and S[ns+1] != -1 :
                ns+= 1
                
            recursion(ns+1, depth + 1)
            S[e], S[s] = -1, -1
            visited[i] = 0
        

recursion(0, 0)
print(-1)

---

시간복잡도

• 극단적으로 시간복잡도를 계산한다면 매번 재귀마다 탐색하는 원소의 수가 1개씩 줄기 때문에
  $N*N-1*N-2...*2*1 = N!$ 정도로 추측이 가능하다.
• 실제로는 이보다 훨씬 작은 숫자이지만 극단적인 최악의 경우를 탐색했을 때 8! * 최대 자리 수(8) = $3*10^5$ 정도가 소요된다고 볼 수 있다. 따라서 약 $O(10^)$의 시간복잡도로 여유롭게 문제를 풀이할 수 있다.