[Python/파이썬] 백준 10597번 순열장난

10597번: 순열장난

 

코드

arr = input()
# 최대 수 N 구하기
if len(arr) < 10:
    max_num = len(arr)
else:
    max_num = (len(arr)-9)//2+9


def find_seq(arr, seq):
    if len(arr) == 0:
        # 1~N까지의 수로 이루어진 순열인지 확인
        sorted_seq = sorted(seq)
        possible = True
        for i in range(1, len(sorted_seq)):
            if sorted_seq[i] != sorted_seq[i-1]+1:
                possible = False
                break
        if sorted_seq[0] == 1 and possible:
            print(*seq)
            exit()
        return
    # 1글자 수
    if int(arr[0]) not in seq:
        find_seq(arr[1:], seq+[int(arr[0])])
    # 2글자 수
    if len(arr) >= 2 and int(arr[:2]) <= max_num and int(arr[:2]) not in seq:
        find_seq(arr[2:], seq+[int(arr[:2])])


find_seq(arr, [])

 

백트래킹을 이용하여 입력으로 주어진 수열을 분리한다. 

 

절대 순열의 요소가 될 수 없는 요소들을 가지치기 해주어야 시간 초과를 막을 수 있다. 숫자가 1글자, 2글자인 케이스 2개로 나누어 가지치기를 시행할 수 있다.

 

1. 1글자 수를 분리할 때

seq는 이전까지 arr에서 분리한 수들을 모아 놓은 집합이라고 할 수 있다. 그렇기에 이 seq에 이미 있는 수가 또 들어가면 순열을 이룰 수 없기 때문에 seq에 없는 수만 분리해서 넣을 수 있다.

 

2. 2글자 수를 분리할 때

3가지 조건을 만족해야 함수를 재귀적으로 호출하며 다음으로 넘어갈 수 있다.

 

①남아있는 수열의 길이가 2 이상

②분리할 수가 최대 값인 가능한 최대값인 max_num보다 크지 않을 것

③seq에 아직 없는 수일 것

 

max_num은 처음 입력받은 수열의 길이로 알 수 있다. 수열의 길이가 10 미만의 길이라면 1글자 수들로만 이루어진 순열이었을 것이고, 그 이상이라면 2글자 수들도 섞인 것인데 순열은 최대 50까지의 수들로 이루어져 있으므로 최대 수는 arr의 길이에서 1글자 수들의 개수인 9개를 빼고 2로 나눈 값에 다시 1글자 수들의 개수 9를 더한 값이다.