[백준] 10973번 이진 순열 [Python]

 

 

 

 

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N$(1 ≤ N ≤ 10,000)$이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

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

 

시간 초과
실제 순열을 구해서 주어진 순열의 이전 순열을 출력하는 방식은 시간 초과가 나오네요 ㅎㅎ

import sys
from itertools import permutations
N = int(sys.stdin.readline())
pm = tuple(map(int, sys.stdin.readline().split()))
tmp = []
for i, p in enumerate(permutations(range(1,N+1),N)):
    if p == pm:
        print(" ".join(map(str, tmp)) if tmp else '-1')
        break
    tmp = p

 

설명을 적어봤는데, 복잡하네요.

 

사전식 배열 순서에서 현재 순열과 앞의 순열의 차이점을 찾아야합니다.

앞의 순열을 구하기 위해 더 낮은 순번이 되도록 두 숫자의 자리를 바꾸고,

그 중에서는 가장 큰 숫자가 되도록 $($바로 앞의 순열이 되도록$)$ 그  뒤의 숫자들은 내림차순으로 정렬합니다.

 

어떤 자리의 숫자를 서로 바꾸는지를 찾아야하는데,

사전식 배열에서 더 낮은 순번의 순열을 구하기 위해서

앞에 있는 큰 값을 뒤에 있는 작은 값과 바꿔야합니다.

큰 값을 ,a, 작은 값을 b라고 합시다.

 

그래서 뒤에서부터 살펴보면서 큰 값-작은 값 순서로 배열된 큰 값 = a을 찾아야 합니다.

그런 관계가 없으면 1부터 N까지 오름차순으로 정렬된 첫번째 순열이라서 -1을 반환합니다.

발견하면 큰 값은 정해졌고, 작은 값은 바로 앞의 순열을 구해야하기 때문에 다시 한 번 탐색을 해야합니다.

 

작은 값은 현재 구한 것 보다 더 뒷 자리에 a보다 작은 수가 존재할 수 있기 때문에

다시 한 번  뒤에서부터, 이번에는 그냥 a보다 작은 수 = b를 찾아서 가장 먼저 발견되는 숫자를 찾습니다.

 

a와 b의 자리를 바꾸고,

첫번째 자리부터 원래 a가 있던 자리까지는 $($현재는 b가 있는 자리$)$ 숫자를 그대로 배치하고

그 이후는 오름차순으로 정렬해서 주어진 순열의 바로 앞 순열을 찾습니다.

 

3 5 2 1 4를 예를 들면, 이전 순열은 3 5 1 4 2 입니다.

주어진 순열 3 5 2 1 4의 뒷자리부터 앞자리로 탐색하면서

현재 숫자와 바로 앞 숫자와 비교해서 증가하는 2 1 과 같은 순서가 있을 때, $($여기서는 세 번째와 네 번째 자리$)$

2 보다 작은 숫자를 찾는데, 주어진 순열의 뒤에서부터 먼저 나오는 수로 합니다.

그 수는 여기서 1인데, 1과 2의 자리를 바꾸고

2의 원래 자리$($세 번째 자리$)$까지는 그대로 두고, 그 뒤의 순서를 내림차순으로 정렬합니다.

>>> 3 5 1 2 4

 

import sys
def f():
    N = int(sys.stdin.readline())
    pm = list(map(int, sys.stdin.readline().split()))
    for i in range(-1,-N,-1):
        # 맨 뒷자리부터 확인할 때, 앞자리가 더 큰 경우가 있으면 
        if pm[i-1] > pm[i]:
            for j in range(-1,-N,-1):
                # 뒤에서 부터 그 숫자보다 더 작은 숫자가 있는지 확인해서 
                if pm[j] < pm[i-1]:
                    # 그 숫자와 자리를 바꾸고
                    pm[i-1], pm[j] = pm[j], pm[i-1]
                    # i-1번째 까지는 그대로 유지하고 그 뒤로는 내림차순 정렬
                    pm = pm[:i] + sorted(pm[i:], reverse=True)
                    return " ".join(map(str, pm))
    # 맨 뒷자리부터 확인할 때, 앞자리가 더 큰 경우가 전혀 없으면 첫번째 순열이라서 -1 반환
    else: return -1
print(f())

 

예제 입력 1 

4
1 2 3 4

예제 출력 1 

-1

예제 입력 2 

5
5 4 3 2 1

예제 출력 2 

5 4 3 1 2