숌 사이 수열

제목: 숌 사이 수열
번호: 1469
푼 날짜: 2024-01-28

문제는 여기에서 확인 가능합니다.

문제 내용 보기 (click me!)

문제

숌은 N개의 다른 숫자로 구성된 집합 X를 만들었습니다. 이제 길이가 2N인 숌 사이 수열 (S)을 만들려고 합니다.

숌 사이 수열의 정의:

  1. X에 있는 모든 숫자는 숌 사이 수열 S에 정확히 두 번씩 나타나야 합니다.
  2. X에 있는 숫자 i에 대해, S에서 i가 두 번 나타나는 사이에는 정확히 i개의 숫자가 있어야 합니다.

예시:
집합 X가 {1, 2, 3}일 때, 가능한 숌 사이 수열은 {2, 3, 1, 2, 1, 3}입니다. 이 수열은 위 정의를 모두 만족합니다.

문제:
집합 X가 주어졌을 때, 가능한 숌 사이 수열 S를 하나 출력하십시오.

입력

  • 첫 번째 줄에는 집합 X의 크기 N이 주어집니다.
  • 두 번째 줄에는 X에 속하는 수가 공백으로 구분되어 주어집니다.
  • N의 크기는 8 이하의 자연수입니다.
  • X의 원소는 0 이상 16 이하의 정수입니다.

출력

  • 가능한 숌 사이 수열을 공백으로 구분하여 출력합니다.
  • 여러 개의 가능한 수열이 있는 경우, 사전 순으로 가장 빠른 수열을 출력합니다.
  • 가능한 수열이 없는 경우 -1을 출력합니다.

예제

입력 1

3
1 2 3

출력 1

2 3 1 2 1 3

입력 2

1
0

출력 2

0 0

입력 3

4
1 2 3 4

출력 3

2 3 4 2 1 3 1 4

입력 4

5
1 2 3 4 5

출력 4

-1

입력 5

2
2 0

출력 5

2 0 0 2

입력 6

8
0 4 13 12 8 5 2 14

출력 6

-1

풀이

BLANK = -1

def dfs(count: int, N: int, S: list[int], X: list[int]):
    if count == N:
        print(*S)
        exit()
    
    for i in X:
        if i in S:
            continue
        next_idx = S.index(BLANK)
        if next_idx + i + 1 >= N * 2:
            break
        if S[next_idx + i + 1] != BLANK:
            continue

        S[next_idx] = i
        S[next_idx + i + 1] = i
        dfs(count+1, N, S, X)
        S[next_idx] = BLANK
        S[next_idx + i + 1] = BLANK

def solve(N: int, X: list[int]):
    S = [BLANK] * (N * 2)
    dfs(0, N, S, X)
    print(-1)

N = int(input())
X = sorted(list(map(int, input().split())))
solve(N, X)

언어: Python

알고리즘: DFS

시간 복잡도: O(N!)

난이도: GOLD 5

문제 해설

사전순으로 가장 빠른 숌 사이 수열을 만드는 문제다.
숌 사이 수열의 정의는 아래와 같다.

서로 N 개로 이루어진 X의 요소가 모두 2번씩 존재해야 하고,
어떤 수가 i 라면, i 와 i사이에는 어떤 수가 i 개 등장해야 된다.

Example1
When: 
    N = 2
    X = {2, 0}
Then:
    S = {2, 0, 0, 2}

Example2
When: 
    N = 3
    X = {2, 3, 1}
Then:
    S = {2, 3, 1, 2, 1, 3} 또는 {3, 1, 2, 1, 3, 2}

2번째 예시처럼 가능한 경우의 수가 여러개일 수 있다.
그런경우 사전순으로 가장 앞에 있는걸 출력해야 한다.

나는 아래와 같이 접근했다.

  1. 필요한 값 N, X 를 입력받는다.
    •  N = int(input())
 X = sorted(list(map(int, input().split())))
    • X 는 오름차순으로 정렬해서 받아줬다.
    • 사전순으로 가장 빠른것부터 시도하기 위함.
  2. 만들어야 될 수열 S 는 빈칸으로 채워준다.
    •  BLANK = -1
 S = [BLANK] * (N * 2)
 # S: {-1, -1, -1, -1, -1, -1}
  3. 그 후 사전순서로 앞부터 수열 S를 채우는 함수를 재귀적으로 호출한다.
    • X를 정렬했으므로, 사전 순서로 채우는게 보장된다.
    • 아래와 같이 동작한다.
    •   입력값: 
  N = 3
  X = {1, 2, 3}

  S = {-1, -1, -1, -1, -1, -1}
        
  동작:
  i = 1, S = {1, -1, 1, -1, -1, -1}
      ㄴ i = 2, S = {1, 2, 1, -1, 2, -1}
          ㄴ i = 3, S =  {1, 2, 1, 3, 2, -1} . 3 # 범위를 벗어남 불가능
      ㄴ i = 3, S = {1, 3, 1, -1, 3, -1}
          ㄴ i = 2, S = {1, 3, 1, 2, 3, -1} 2  # 범위를 벗어남 불가능
  i = 2, S = {2, -1, -1, 2, -1, -1}
      ㄴ i = 1, S = {2, 1, -1, "2! 1!", -1, -1} # 채워야 할 곳에 2 가 있어서 불가능
      ㄴ i = 3, S = {2, 3, -1, 2, -1, 3}
          ㄴ i = 1, S = {2, 3, 1, 2, 1, 3} # 종료 조건을 타고 탈출함

  정답 : 2 3 1 2 1 3

시간 복잡도

위 코드는 한가지를 고르고 나머지 가능한 경우를 하나씩 줄여가며 재귀적으로 탐색하고 있다.
즉 N 팩토리얼이다. N 이 최대 8 까지 주어지므로
최악의 경우 8! = 40320 으로 2초내에 충분이 풀이가 가능하다고 생각되어,
풀었고 풀이에 성공했다.

capture

주의 할 점

정렬에 대해 주의하자.
만약 여러 개일 경우 사전 순으로 가장 빠른 것을 출력한다.
이 부분이 애매했다.
처음에는 계속 문자열로 처리를 해서 계속 틀렸다.

즉 문제에서 요구하는 조건을 충족하려면
반드시 숫자로 비교해야 한다.

capture
위 이미지 처럼 정렬을 문자열로 하면,
‘10’ 이 가장 사전순으로 앞이다.

근데 사전순이라면 문자열로 기준잡는거 아닌가…