백준 파이썬 10597번

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

N 구하기

1. 수열 길이가 9 이하면 N == 수열 길이
2. 11 이상부터는 N >= 10

따라서 코드로 작성하면 다음과 같다.

n = len(word) if len(word) <= 9 else 9 + (len(word) - 9) // 2

백트래킹 조건

순열을 저장하는 리스트를 만들어 관리한다.

한 자리수

1. 0이 아니어야함 -> 순열이 1~N으로 이루어져있으니까
2. 리스트에 이미 있는지 확인

두 자리수

1. 해당 숫자가 N보다 작거나 같아야 함
2. 리스트에 이미 있는지 확인
3. 10의 자리수가 0이 아니어야함

3번을 처리 안해줘서 계속 오답이 났었다.

코드

import sys

input = sys.stdin.readline
word = input().rstrip()
n = len(word) if len(word) <= 9 else 9 + (len(word) - 9) // 2
answer = list()

def backtracking(index: int):
    if index == len(word):
        print(' '.join(answer))
        exit(0)
    if word[index] != '0' and word[index] not in answer:
        answer.append(word[index])
        backtracking(index + 1)
        answer.pop()

    if word[index] != '0' and int(word[index: index + 2]) <= n and word[index:index + 2] not in answer:
        answer.append(word[index:index + 2])
        backtracking(index + 2)
        answer.pop()

backtracking(0)

exit(0) 으로 한 번 출력하고 프로그램을 종료시킬 수 있다.