파이썬으로 사전순으로 가장 큰 유효한 시퀀스 구성하기

숫자 n이 주어졌을 때, 아래 세 가지 규칙을 모두 만족하는 수열을 찾아야 합니다.

• 1은 수열 안에 정확히 한 번만 등장합니다.
• 2부터 n 사이의 모든 숫자는 각각 두 번씩 등장합니다.
• 2부터 n까지의 각 숫자 i에 대해, i가 등장하는 두 위치 사이의 거리는 정확히 i여야 합니다.

여기서 수열 내 두 숫자 a[i]와 a[j] 사이의 거리는 |j − i|로 정의됩니다. 그리고 이러한 조건을 만족하는 수열 중 사전순(lexicographically)으로 가장 큰 수열을 구하는 것이 목표입니다.

예를 들어 입력이 n = 4라면 출력은 다음과 같습니다.

[4, 2, 3, 2, 4, 3, 1]

문제 해결 접근 방법

이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 사전순으로 가장 큰 수열을 만들기 위해, 큰 숫자부터 우선적으로 배치합니다.
• 빈 자리(start)마다 남은 숫자들을 하나씩 넣어보고, 배치가 불가능하면 이전 상태로 되돌아갑니다.
• 모든 숫자를 성공적으로 배치하면 탐색을 종료하고 결과를 반환합니다.

백트래킹 함수의 동작 단계

1. backtrack(elems, res, start=0) 함수를 정의합니다.
2. 남은 숫자 목록 elems가 비어 있으면 True를 반환합니다. (모든 숫자 배치 완료)
3. start가 결과 배열 res의 길이 이상이면 False를 반환합니다.
4. res[start]가 이미 채워져 있다면(-1이 아니라면) 다음 위치로 이동합니다.
5. elems의 각 숫자에 대해 다음을 시도합니다.
   • 숫자가 1이면 거리(dist)는 0, 그 외에는 숫자 값 자체가 거리가 됩니다.
   • start + dist가 배열 범위 내에 있고 해당 위치가 비어 있다면(-1이라면), 양쪽 위치에 숫자를 배치합니다.
   • 배치 후 재귀 호출이 실패하면 배치를 되돌리고(백트래킹) 다음 숫자를 시도합니다.
   • 재귀 호출이 성공하면 즉시 True를 반환합니다.

메인 로직

• elems: n부터 1까지 내림차순으로 정렬된 리스트 (큰 숫자부터 시도하여 사전순 최대 보장)
• res: 길이가 n×2−1이고 −1로 초기화된 결과 배열
• backtrack(elems, res) 호출 후 res를 반환합니다.

구현 예제

다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.

def backtrack(elems, res, start = 0):
   if len(elems) <= 0:
      return True

   if start >= len(res):
      return False

   if res[start] != -1:
      return backtrack(elems, res, start + 1)

   for i in range(len(elems)):
      num = elems[i]
      dist = 0 if num == 1 else num

      if (start + dist) < len(res) and res[start + dist] == -1:
         res[start] = num
         res[start + dist] = num
         elems.pop(i)

         if not backtrack(elems, res, start):
            res[start] = -1
            res[start + dist] = -1
            elems.insert(i, num)
            continue
         else:
            return True

def solve(n):
   elems = [ i for i in range(n,0,-1)]
   res = [ -1 for i in range(n*2 - 1)]
   backtrack(elems, res)
   return res

n = 4
print(solve(n))

입력

4

출력

[4, 2, 3, 2, 4, 3, 1]

출력 결과를 살펴보면, 숫자 4는 인덱스 0과 4에 위치해 거리가 4이고, 숫자 3은 인덱스 2와 5에 위치해 거리가 3, 숫자 2는 인덱스 1과 3에 위치해 거리가 2이며, 숫자 1은 한 번만 등장합니다. 또한 큰 숫자부터 앞쪽에 배치되어 사전순으로 가장 큰 수열임을 확인할 수 있습니다.