[BOJ/PYTHON] 10597. 순열장난

백준 문제 링크: https://www.acmicpc.net/problem/10597

문제 요약

공백이 사라진 수열이 주어질 때, 복구된 수열 출력

순열은 1부터 N까지의 수로 이루어짐. 모두 10진수이고 공백으로 분리됨

핵심 아이디어

1부터 N까지의 수로 이루어진 “순열”이기 때문에 인풋의 길이로 순열의 마지막 숫자를 짐작할 수 있다.

인풋의 길이가 10보다 작으면 순열은 1부터 인풋의 길이까지만큼으로 이루어져있다.

인풋의 길이가 10보다 크면 1~9까지의 한 자리 수인 경우와 10부터의 두 자리 수인 경우로 나뉜다. 그러면 인풋의 길이에서 1~9의 경우인 9개를 뺀 후, 그 수를 2로 나누면 된다. 1~9를 뺀 나머지는 다 두 자리 수일 거라 2로 나누면 그 수들이 총 몇 개인지 나온다.

식으로 정리하면 다음과 같다.

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

백트래킹으로 풀면 된다. 앞자리가 0이 아니면 한 자리 수와 두 자리 수 케이스 각각을 백트래킹해준다. 인풋의 길이만큼 다 봤으면 출력하고 끝내주면 된다.

풀이

# silver1-10597. 순열장난

import sys
input = sys.stdin.readline

nums = input().rstrip()
array = []

# 앞자리수 0 아니게 하면 될 듯
# 1부터 순서대로 다 있는 순열이니까 길이가 9 이하면 1부터 n까지 있는 것
# 길이가 10 이상이면 길이에서 1~9의 경우인 9를 뺌. 그리고 그 수에서 2씩 나누면 됨 (두 자리 수로 이뤄져 있으니까)
if len(nums) < 10: 
    n = len(nums)
else:
    n = 9 + (len(nums) - 9) // 2

def back(i):
    if i == len(nums):
        print(*array)
        exit()
    if nums[i] != "0": # 앞자리가 0이 아님
        single = nums[i] # 한자리수
        double = nums[i : i + 2] # 두자리수
        # 한자리수
        if int(single) <= n and single not in array:
            array.append(single)
            back(i + 1)
            array.pop()
        # 두자리수
        if int(double) <= n and double not in array:
            array.append(double)
            back(i + 2)
            array.pop()            

back(0)

print(array)

Trouble Shooting

한 자리 수 케이스를 if, 두 자리 수 케이스를 elif로 했더니 틀렸다. 둘 다 봐야 한다.

실행 시간

메모리 31388KB, 시간 124ms (python3)