[백준 10972] 다음 순열

문제 출처 : https://www.acmicpc.net/problem/10972

10972번: 다음 순열

permutations 함수를 사용하면 쉽게 해결 가능한 문제로 보입니다. permutations에 대해 잘 모른다면 다빈치코딩 알고리즘 브루트포스를 확인 바랍니다. 하지만 막상 해결이 쉽지 않습니다.

무작정 해보기

for문을 통해 순열들을 호출해서 입력된 배열과 비교하여 같은 것이 나올 때까지 찾습니다. 같은 것이 나오면 마지막 순열이면 -1을 출력하고, 아니면 다음 순열을 출력하면 됩니다. 하지만 막상 이렇게 풀면 시간초과가 됩니다. 시간초과가 되지만 permutations 함수를 사용하는 방법부터 알아 보겠습니다.

입력 받기

from itertools import permutations

N = int(input())
arr = tuple(map(int, input().split()))

순열의 개수 N과 다음 순열을 찾을 arr을 입력 받습니다.

permutations 함수 사용하기

def solve():
    check = False
    for per in permutations(range(1, N+1), N):
        if check:
            print(*per)
            return

        if arr == per:
            check = True

    print(-1)
    return

solve()

permutations 함수로 순열을 만들어 냅니다. 만들어진 순열인 per와 arr을 비교하여 같으면 다음 순열을 출력하고 다음 순열이 없으면 -1을 출력하도록 하였습니다. 예제는 잘 나오지만 제출을 하면 시간초과임을 알 수 있습니다. 이 방법이 아닌 다른 방법으로 구현해야 이 문제를 해결할 수 있습니다.

직접 구하기

c++에는 next_permutation이라는 함수가 있어 다음번째 순열을 쉽게 찾을 수 있지만 파이썬에는 그런 함수가 없습니다. 따라서 순열이 어떤 규칙을 가지고 있는지 알아야 합니다. 문제에 있는 예제인 3개는 규칙을 알아보기에 너무 적기 때문에 7개로 확인해 보겠습니다.

1, 2, 3, 4, 5, 6, 7

첫 번째 순열 입니다. 이 순열의 다음은 아래와 같습니다.

1, 2, 3, 4, 5, 7, 6

규칙성을 알아보기 위해 순열을 몇 개 더 보여 드리겠습니다

1, 2, 3, 4, 6, 5, 7

1, 2, 3, 4, 6, 7, 5

1, 2, 3, 4, 7, 5, 6

1, 2, 3, 4, 7, 6, 5

규칙을 찾으셨나요? 순열의 규칙은 뒤에서부터 오름차순을 만들려고 하는 것입니다. 그래서 최종적으로 뒤에서부터 확인했을 때 더이상 오름차순이 되지 않으면 모든 순열을 다 찾은것이 되는 것입니다.

7, 6, 5, 4, 3, 2, 1

이렇게 뒤에서부터 보면 오름차순이고 앞에서부터 보면 내림차순으로 정렬된 것이 마지막 순열 입니다. 그럼 1, 2, 3, 4, 7, 6, 5에 이어서 다음 순열을 찾아 보겠습니다.

1, 2, 3, 4, 7, 6, 5

뒤에서부터 오름차순을 이어나가다보니 뒤에서부터 3개의 오름차순이 완성 되었습니다. 더 이상 오름차순 정렬이 되지 않을 때에는 뒤에서부터 4번째 자리를 포함 시켜줍니다. 범위 밖에 있는 4와 이전 범위 3개중 4보다 큰 가장 작은 숫자를 교환 합니다.

1, 2, 3, 4, 7, 6, 5

4와 4보다 큰 숫자 중 가장 작은 5를 교환 한 뒤 정렬합니다.

1, 2, 3, 5, 4, 6, 7

이제 뒷 부분인 [4, 6, 7]부분이 뒤에서 볼 때 오름차순이 되도록 [7, 6, 4]로 만들어 주면 됩니다. 그러기 위해서 [4, 6, 7] → [4, 7, 6] → [6, 4, 7] → [6, 7, 4] → [7, 4, 6] → [7, 6, 4] 순서로 변경이 됩니다.

1, 2, 3, 5, 7, 6, 4

뒤에서 부터 오름차순이 끝난 다음 수인 5와 5보다 큰 가장 작은 숫자인 6을 교환 합니다. 그리고 나머지를 정렬 합니다.

1, 2, 3, 6, 4, 5, 7

이제 어느정도 규칙을 알았으니 임의의 숫자의 다음 순열을 생각해 보겠습니다.

5, 3, 1, 6, 7, 4, 2

이와 같은 숫자의 다음 순열을 생각해 보겠습니다. 먼저 뒤에서부터 오름차순 정렬이 어디까지 되어 있나 확인합니다.

5, 3, 1, 6, 7, 4, 2

뒤에서부터 보면 2, 4, 7까지가 정렬 되어 있기 때문에 6을 변경시켜 주어야 합니다. 그리고 6보다 큰 가장 작은 수인 7을 교환 합니다. 그리고 나머지 숫자를 정렬 합니다.

5, 3, 1, 7, 2, 4, 6

규칙 확인

그럼 위에서 직접 구한 다음 순열의 규칙을 확인해 보겠습니다.

 

1. 뒤에서부터 오름차순이 어디까지 되어 있는지 확인 합니다.
2. 오름차순이 끝나는 숫자 a 와 a보다 큰 가장 작은 숫자를 교환합니다.
3. a 이후의 숫자들을 정렬 합니다.

이것이 바로 다음 순열을 구하는 방법 입니다. 자 그럼 이것을 직접 코드로 작성해 보겠습니다.

입력 받기

N = int(input())
arr = list(map(int, input().split()))

입력은 이전과 똑같이 받습니다.

오름차순 확인하기

뒤에서부터 오름차순의 끝이 어딘지 확인 합니다.

def next_permutation(arr):
    i = N - 1
    while 0 < i and arr[i - 1] >= arr[i]:
        i -= 1

    if i <= 0:
        print(-1)
        return

arr[i - 1] 과 arr[i]을 비교하여 arr[i]이 더 크다면 뒤에서부터 진행되는 오름차순이 끝났다는 뜻입니다. 그 때의 arr[i - 1]의 값을 기억합니다. 이 값이 바꿔줄 수 a 입니다. 만약 i값이 0이 되거나, 0보다 작다면 뒤에서부터 끝까지 오름차순 정렬이 되어있다는 뜻이기 때문에 사전순 마지막이라는 뜻이고, -1을 출력하고 함수를 끝내줍니다.

a보다 큰 가장 작은 수 찾아 교환하기

arr[i - 1]이 a라고 하였습니다. 이 숫자보다 작은 가장 작은 수를 찾습니다. 방법은 뒤에서부터 비교하여 arr[i - 1]보다 큰 숫자가 나올 때까지 j값을 줄여주면 됩니다. 그렇게 찾은 arr[j]값과 arr[i - 1]의 값을 교환하면 됩니다.

    while arr[i - 1] >= arr[j]:
        j -= 1
    
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

나머지 숫자 정렬하기

교환이 완료 되면 a 이후의 숫자들을 정렬합니다. a가 arr[i - 1]이기 때문에 arr[i] 부터 정렬하면 됩니다. 그리고 완성된 순열의 숫자들을 출력하면 됩니다.

    arr = arr[:i] + sorted(arr[i:])
    print(*arr)
    return

next_permutation(arr)

전체 코드

그럼 전체 코드를 확인해 보겠습니다.

N = int(input())
arr = list(map(int, input().split()))

def next_permutation(arr):
    i = N - 1
    while 0 < i and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        print(-1)
        return 
    
    j = N - 1
    while arr[i - 1] >= arr[j]:
        j -= 1
    
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    arr = arr[:i] + sorted(arr[i:])
    print(*arr)
    return

next_permutation(arr)