[python] 백준 10597번 : 순열 장난(backtracking)

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

10597번: 순열장난

 

우선 1부터 N까지 구성된 수열을 복구하기 위해서는

N보다 큰 숫자는 제외하고 N까지만 찾아야 하기 때문에 N이 무엇일지 알아야 한다.

N은 주어진 문자열 kriii = '4111109876532' 의 길이를 통해 찾을 수 있다.

 

문자열의 길이가 10보다 작은 경우 

N = len(krii)

 

문자열의 길이가 10보다 클 경우 

N = 9 + (len(krii)-9)//2

 

예를들어, 문자열이 '123456789'라면 > N은  9

                            '12345678910111213'라면 > N은 (17-9)//2 + 9 = 13

 

[성공한 코드]

import sys
sys.stdin = open('10957.txt', 'r')


def dfs(index, arr):
    if index == len(kriii):
        print(*arr)
        exit()

    # 1자리수 check
    num1 = int(kriii[index])
    if not visited[num1]:
        visited[num1] = True
        arr.append(num1)
        dfs(index + 1, arr)
        visited[num1] = False
        arr.pop()

    # 2자리수 check
    if index+1 < len(kriii):
        num2 = int(kriii[index:index+2])
        if num2 <= N and not visited[num2]:
            visited[num2] = True
            arr.append(num2)
            dfs(index+2, arr)
            visited[num2] = False
            arr.pop()


kriii = input()
N = len(kriii) if len(kriii) < 10 else 9 + (len(kriii) - 9) // 2
visited = [0 for _ in range(N + 1)]

dfs(0, [])