(Python/🥇5)백준알고리즘 10597번: 순열장난

 

문제 바로가기 

문제:

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순열을 복구하도록 도와주자.

입력:

첫 줄에 공백이 사라진 kriii의 수열이 주어진다. kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

 

출력:

복구된 수열을 출력한다. 공백을 잊으면 안 된다. 복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

 

다시 알고리즘도 가보려고 합니다 !

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

numbers = str(input())

lst = []
idx = 0

if len(numbers) < 10:
    n = len(numbers)
else:
    n = 9 + (len(numbers) - 9) // 2

def bt(num):
    if num == len(numbers):
        print(*lst)
        exit()

    if numbers[num] != "0":
        one = numbers[num]
        two = numbers[num:num+2]

        if int(one) <= n and one not in lst:
            lst.append(one)
            bt(num+1)
            lst.pop()
        if int(two) <= n and two not in lst:
            lst.append(two)
            bt(num+2)
            lst.pop()
bt(0)

 

 

순열은 n개의 원소를 순서에 상관 있게 나열합니다.

 

최대로 나올 수 있는 n은 1~9 에 9개를 빼주고 2자릿수는 2개씩 차지하니 2를 나눠주면 됩니다.

 

그러면 결국 복구한 순열은 1자리 아니면 2자리가 되니. 그거를 백트래킹으로 죽여줍니다.