숌 사이 수열 ( 1469 번 )

1469번: 숌 사이 수열

 

---

🧠 알고리즘

• 백트래킹 기반 시뮬레이션

 

✔️ 동작 방식

• -1로 초기화된 배열 shom, 숫자 사용 여부 체크용 딕셔너리 use_check
• 백트래킹 실행
• 현재 인덱스 i에 배치하고, i + num + 1 위치도 빈칸이라면 같은 숫자 배치
• 실패 시 원상복구 (rollback)
• 모든 칸이 채워지면 조건 만족 → 정답 수열 리턴

---

 

🧾 코드

import sys

# 백트래킹
def _back(n, n_list, shom, use_check):
    if -1 not in shom:
        return shom

    start_idx = shom.index(-1)
    for num in n_list:
        if not use_check[num]:
            end_idx = start_idx + num + 1
            if (end_idx < n * 2) and (shom[end_idx] == -1):
                use_check[num] = True
                shom[start_idx], shom[end_idx] = num, num

                gogo = _back(n, n_list, shom, use_check)
                if gogo:
                    return gogo

                use_check[num] = False
                shom[start_idx], shom[end_idx] = -1, -1

    return False


def _main(n, n_list):
    n_list.sort()
    shom = [-1] * n * 2
    use_check = {i: False for i in n_list}

    answer = _back(n, n_list, shom, use_check)
    if not answer:
        return -1

    return ' '.join(map(str, answer))
    

n = int(sys.stdin.readline().rstrip())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))

print(_main(n, n_list))

---

 

⏱️ 시간 복잡도

def _back(n, n_list, shom, use_check) : 백트래킹 알고리즘 ( 가능한 모든 경우를 탐색 )
	if (end_idx < n * 2) and (shom[end_idx] == -1) : 조건 탐색을 통한 가지치기

가지치기를 하지만 최악의 경우 모든 조건을 탐색.. 
해당 알고리즘 시간 복잡도 : 팩토리얼 시간 복잡도 ( O(n!) )