1469. [Python]숌 사이 수열

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 브루트 포스
• 백트래킹

 

3. 파이썬 코드

 

import sys
# 재귀 제한 해제
sys.setrecursionlimit(10000)
# 백트래킹
def backtracking(cnt):
    # 리스트 2배의 길이가 됐을때 종료
    if cnt == N*2:
        print(*answer)
        exit()
        return
    # 리스트 안의 값 순회
    for value in num_list:
        # 딕셔너리 값이 존재할 경우
        if num_dict[value] > 0:
            # 딕셔너리 값이 2인 경우 백트래킹
            if num_dict[value] == 2:
                answer.append(value)
                num_dict[value] -= 1
                backtracking(cnt+1)
                answer.pop()
                num_dict[value] += 1
            # 이미 한번 나온 경우
            elif num_dict[value] == 1:
                # 현재 값의 인덱스 위치 찾기
                idx = answer.index(value)
                # 현재 cnt 값에서 idx + 1 한 값이 현재 값과 같은경우 같은수이므로 백트래킹
                if cnt - (idx + 1) == value:
                    answer.append(value)
                    num_dict[value] -= 1
                    backtracking(cnt+1)
                    answer.pop()
                    num_dict[value] += 1


N = int(input())
num_list = list(map(int, input().split()))
# 사전 순 먼저 나온것이므로 숫자 정렬
num_list.sort()
num_dict = {}
# 초기 딕셔너리 2로 고정
for i in num_list:
    num_dict[i] = 2

answer = []
# num_list 내부 순회 백트래킹
for i in num_list:
    answer = [i]
    num_dict[i] -= 1
    backtracking(1)
    num_dict[i] += 1
else:
    print(-1)

 

4. 문제를 풀고난 후 생각

 

• 처음 접근할 때 index 를 통한 접근을 진행했다가 들어오는 값을 바탕으로 딕셔너리를 구성해야 하는것을 뒤늦게 깨닫고 코드를 수정했다.
• 백트래킹을 진행하는 과정에서 불필요한 연산을 줄이기 위해 딕셔너리 값을 이용하여 가지치기를 진행했다. 또한 사전 순으로 가장 빠른 것을 출력해야 했기 때문에 기존 리스트를 sort 처리하여 정렬한 후 연산을 진행함
• 딕셔너리 값이 2인 경우 백트래킹 진행, 1인 경우 현재 cnt 값을 통한 몇번째 인덱스를 저장할 차례인지 체크 후 현재 값의 인덱스 위치를 구하여 뺀 값이 현재 value 값과 같은 경우 그 사이 value 의 숫자가 존재하기 때문에 백트래킹 진행 외의 경우 연산하지 않음을 구현했다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트 포스
• 백트래킹