[백준 10597] 순열장난

문제

1부터 N까지의 수열이 주어져있다. 이 수열이 공백없이 주어졌을 때 공백을 부분부분에 추가하여 1부터 N까지의 수열이 될 수 있도록 만들어보자.

 

입력

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

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

 

출력

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

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

---

접근

최대 50개의 수로 이루어지기 때문에 각각의 수가 50을 넘기면 안된다. 

또한 한 번 나온 수가 뒤에서 또 나오면 안되고 최종적으로 만들어진 수열의 길이가 수열의 최댓값과 같아야한다.

이 조건에 맞게 구현하였다.

 

구현

- 현재까지 선택한 수의 길이가 처음에 입력한 숫자문자열의 길이와 같다면 올바른 수열인지 검사한다.

- 만들어진 수열의 최댓값과 수열의 길이가 같다면 출력한다.

- 이제 수열을 만들기위해 현재 수만 선택하거나 현재수와 그 다음 수를 선택하여 두 자릿수를 만드는 경우로 나눈다.

- 해당 수가 이전에 나오지 않았다면 선택하고 다음으로 넘어간다.

- 이때 현재 숫자만 선택했다면 picked+1, 두 개의 숫자를 선택했다면 picked+2를 한다.

def solve(picked, numbers):
    if picked == size:
        max_num = max(numbers)
        if max_num == len(numbers):
            print(*numbers)
            exit(0)
        return

    if int(N[picked]) <= 50 and visited[int(N[picked])] == False:
        visited[int(N[picked])] = True
        numbers.append(int(N[picked]))
        solve(picked+1, numbers)
        visited[int(N[picked])] = False
        numbers.pop()

    if picked < size-1 and int(N[picked: picked+2]) <= 50 and visited[int(N[picked: picked+2])] == False:
        visited[int(N[picked: picked+2])] = True
        numbers.append(int(N[picked: picked+2]))
        solve(picked+2, numbers)
        visited[int(N[picked: picked+2])] = False
        numbers.pop()

---

전체 코드

import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

def solve(picked, numbers):
    if picked == size:
        max_num = max(numbers)
        if max_num == len(numbers):
            print(*numbers)
            exit(0)
        return

    if int(N[picked]) <= 50 and visited[int(N[picked])] == False:
        visited[int(N[picked])] = True
        numbers.append(int(N[picked]))
        solve(picked+1, numbers)
        visited[int(N[picked])] = False
        numbers.pop()

    if picked < size-1 and int(N[picked: picked+2]) <= 50 and visited[int(N[picked: picked+2])] == False:
        visited[int(N[picked: picked+2])] = True
        numbers.append(int(N[picked: picked+2]))
        solve(picked+2, numbers)
        visited[int(N[picked: picked+2])] = False
        numbers.pop()

N = input().strip()
visited = [False] * 51
size = len(N)
solve(0, [])