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

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

10597번: 순열장난

Problem

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

조건

• 첫 줄에 공백이 사라진 kriii의 수열이 주어진다.
• kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.
• 복구된 수열을 출력한다. 공백을 잊으면 안 된다.
• 복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

SOL

문제는 짧은데, 풀기가 상당히 까다로웠던 문제이다. 처음에 DP인줄 알았는데, DP라고 하기에는, 그 이전답으로 문제의 답을 구할 수 없게 되어있음. 그래도, 최적화 problem을 해결하는 방법은 backtracking이 있다.

 

Backtracking 문제이다.

 

1~N 까지의 수로 이루어진 순열이 모두 공백으로 분리가 되어있었다. 예를들어, 1~9까지면, {1,2,3,4,5,6,7,8,9} 이런식으로 있었는데, 콤마를 다 빼서, 123456789일거고, 1~10까지면, 12345678910 일 것이다.

이때, 우리가 입력받는 Kriii순열의 길이와, N까지의 관계에 대해서 알아야한다. 왜냐하면, 최대 값이 N까지일거니까, 123456789 이라고해서, 123을 만들면 안되기 때문이다.

 

• 순열의 길이가 10보다 작으면 이는 1자리 숫자로만 구성된 순열이다. 
  • maxN = 배열의 길이
• 순열의 길이가 10보다 크다면, 2자리 숫자와 1자리 숫자가 섞인 순열이다.
  • maxN = 9+(배열의길이-9)//2

예시.

2자리 숫자와 순열의 길이를 알아내기 위해서, 몇가지 예시를 들어보자. 

2자리 숫자를 만드려면, 숫자 2개가 필요하고, 9개(1자리숫자)를 빼고, 남은 숫자를 조합해서 2자리를 만들어야한다.

따라서, maxN = 9+(배열의길이-9)//2

 

끝내는 지점

• flag =True인 순간
• c==maxN인 순간 ( tmp에 완성된 수열을 담고 있을건데, tmp의 index라고 생각하면 편함)

재귀를 하는 조건

• 한자리 숫자
  • 순열이기 때문에, 중복된 숫자가 사용되면 안됨. 이미 사용되어졌다면, 체크할 필요도 없음.
  • 사용하지 않는다면, 다음으로 재귀
• 두자리 숫자
  • 먼저, 범위 chk, 2자리 숫자를 만들 수 있는지(Out of index 방지)
  • 만들 수 있다면, 만들고,해당 숫자가 최댓값을 넘지않고, 사용되지 않았다면 사용.

import sys
input =sys.stdin.readline

def makeKriii(index,c):
    global finish,ans
    if finish:
        return
    if index==len(Kriii):
        if c==maxN:
            finish= True
            ans = " ".join(map(str, tmp))
        return
    # 한자리 숫자, 두 자리 숫자 탐색
    
    num1=int(Kriii[index]) 
    if not arr[num1]: # 사용여부 chk
        arr[num1] = True
        tmp[c] = num1
        makeKriii(index+1,c+1)
        arr[num1] = False
    if index+1<len(Kriii): # 두자리 숫자 chk
        num2 = int(Kriii[index:index+2])
        if num2 < maxN+1 and not arr[num2]:
            arr[num2] = True
            tmp[c] = num2
            makeKriii(index+2, c+1)
            arr[num2] = False

Kriii = input().rstrip()

if len(Kriii)<10:
    maxN=len(Kriii)
else:
    maxN= 9+((len(Kriii)-9)//2)
arr=[0 for _ in range(maxN+1)]
tmp=[0 for _ in range(maxN)]
finish=False
makeKriii(0,0)
print(ans)