[BOJ] 순열 장난 (no.10597)

문제

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

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

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

입력

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

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

출력

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

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

🤔 생각

• 한 숫자당 두자리 이내다.

• 그러므로 재귀 파라미터로 인덱스를 넘기고, 한 함수에서 총 index~index+1 만큼을 체크한다.

• 수가 순열의 최댓값을 넘긴다면 back한다. (최댓값은 수식을 세워서 알 수 있다.)

• 중복되는 수는 없으므로, 캐시 배열로 중복 재귀를 막는다.

📌 내 풀이

import sys
input = sys.stdin.readline

def main():
    def solve(idx):
        if idx == ln:
            print(*ans)
            sys.exit()

        num = ""
        for i in range(idx, idx+2):
            if i >= ln: continue
            num = num + perm[i]

            if (inum := int(num)) > n: continue
            if cache[inum]: continue

            cache[inum] = True
            ans.append(inum)
            solve(i+1)
            cache[inum] = False
            ans.pop()

    perm, ans = input().rstrip(), []
    ln = len(perm)
    n = 9 + (ln-9)//2
    cache = [False]*(n+1)
    solve(0)

if __name__ == "__main__":
    sys.exit(main())