[백준] 10597. 백트래킹_순열장난 - Python

문제

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

입력

첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

출력

복구된 수열을 출력한다. 공백을 잊으면 안 된다.

복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

 

 

★ 시작하기 전에

백트래킹이자, dfs 문제이다.

처음에는 막연했다.. 이거 모든 경우 다 하라는 건가? >>>>>>>>>>>>맞다.. ㅎㅎ;

최대 50이니까 2자리까지가 최대이므로 1칸, 2칸씩 나누면서 조건을 만족하는지 확인해야 한다.

결국! 조건을 적절히 걸어서 재귀적으로 풀어야 한다.

 

 

import sys

input = sys.stdin.readline

data = input().strip()
length = len(data) # 길이를 통해 N의 값을 구해야한다.
k = length
n = 1
while k // ( 10**n - 10**(n-1) ):
    k -= ( 10**n - 10**(n-1) )
    n += 1
N = 10**(n-1) + (k)//n - 1     # 최댓값 먼저 구하자.

check = [0 for _ in range(N)]  # 숫자를 사용했는지 안했는지 확인하는 리스트
result = []
def find(idx, word=[]):
    global result
    if len(word) > N: # 길이보다 길어지면 종료!
        return
    if len(word) == N: # 길이만큼 찻으면 결과값을 넣자
        result.append(' '.join(word))
        return
        
     # 한단계씩 넣는 조건
    if (idx <= length-1) and int(data[idx])>0 :
        a = data[idx]
        if int(a) <= N and check[int(a)-1] == 0: 
            check[int(a)-1] = 1    
            word.append(a)
            find(idx+1, word)
            word.pop()
            check[int(a)-1] = 0
    # 두단계씩 넣는 조건(2자리씩 넣는다)
    if idx+1 <= length-1:
        a = data[idx:idx+2]
        if int(a) <= N and check[int(a)-1] ==0 :
            check[int(a)-1] = 1
            word.append(a)
            find(idx+2, word)
            word.pop()
            check[int(a)-1] = 0
    return
find(0)
print(result[0])

나의 풀이는 계속 틀렸었다..

이유는 0도 따로 넣어서 계산했기 때문이었다. 그래서 조건으로 0 이상을 넣어서 풀었더니.. 간신히 통과

 

 

너무 난잡해 보이는 풀이이고 다음은 깔끔하고 습득하고 싶은 풀이를 추가로 적어봤다. 같이 스터디하는 고수의 풀이!

접근법은 같지만 사용했는지 안했는지와 미리 리스트를 만든다면 더 깔끔하게 풀리는 풀이이다.

import sys

input = sys.stdin.readline

def makeIt(index, c):
    global finish, ans
    if finish: return

    if index==len(num):
        if c==maxN:
            finish = True
            ans = " ".join(map(str, tmp))
        return
    # 한자리 숫자나 두자리 숫자로 탐색
    
    # 깔끔하게 사용했는지 안했는지만 확인하고 append가 아닌 미리 만든 리스트를 바꾸는 방식!
    num1 = int(num[index])
    if not used[num1]:  # 만약 한자리 숫자가 사용되지 않았다면 재귀 ㄱㄱ
        used[num1] = True
        tmp[c] = num1
        makeIt(index+1, c+1)
        used[num1] = False
    if index<len(num)-1:  # 만약 두자리 숫자가 사용되지 않았다면 재귀 ㄱㄱ
        num2 = int(num[index:index+2])
        if num2 < maxN+1 and not used[num2]:
            used[num2] = True
            tmp[c] = num2
            makeIt(index+2, c+1)
            used[num2] = False
            
num = input().strip()
if len(num)<10:
    maxN = len(num)
else:
    maxN = 9+(len(num)-9)//2 # 최댓값을 똑같이 구해준다.
    
used = [0 for _ in range(maxN+1)]
tmp = [0 for _ in range(maxN)]
finish = False
makeIt(0,0)
print(ans)