주어진 순열의 다음 순열을 효과적으로 찾는 방법(next permutation, prev_permutation)

1. 문제

 

10972번: 다음 순열 (acmicpc.net)

10972번: 다음 순열

 

 

2. 풀이

 

1부터 n까지 정수로 구성된 어떤 순열이 주어질때 바로 다음 순열을 찾는 문제

 

예를 들어 1부터 5까지 구성된 순열

 

1 2 3 4 5

1 2 3 5 4

1 2 4 3 5

...

 

5 4 2 3 1

5 4 3 1 2

5 4 3 2 1

 

1 2 3 5 4가 주어지면 1 2 4 3 5라고 답해야한다.

 

단순하게 1부터 n까지 리스트를 만들고 permutations로 순열을 구한다음 현재 순열의 위치를 찾고 다음 순열을 찾아볼 수도 있겠지만..

 

n이 10000까지라 단순하게 찾으면 바로 시간초과

 

순열은 1부터 n까지 n개로 구성된 n!개의 리스트들을 왼쪽부터 오른쪽으로 원소별로 비교해서.. 클수록 뒤에 나열하게 된다.

 

두 순열 3 2 1 4 5랑 3 2 4 1 5를 생각해보자. 어떤 것이 나중에 나오는 순열인가?

 

 

 

0번 원소인 3은 서로 같고, 1번 원소인 2는 서로 같고... 2번 원소인 1과 4가 서로 다르다.

 

2번 원소인 4가 3 2 4 1 5가 더 크므로 나중에 나오는 순열이 된다.

 

그래서 5 4 3 2 1이 가장 마지막에 오는 순열이고 이 다음에 오는 순열은 없다.

 

다음과 같은 순열을 보자.

 

바로 다음 순열을 어떻게 구할 수 있을까?

 

 

 

 

순열을 뒤에서부터 9,8,7,6,5... 읽어가면서 오름차순으로 증가하는지 확인한다.

 

계속 오름차순으로 증가하는 9 8 7 6 5 4 3 2 1 형태면 다음 순열이 존재하지 않는다.

 

왜냐하면 현재 순열의 다음 순열이 존재할려면 어떤 인덱스 i에서 a[i]보다 큰 값이 있을 수 있어야한다.

 

9 8 7 6 5 4 3 2 1을 보면 3번 인덱스 6보다 큰 7,8,9를 3번 위치에 쓸 수 있어야하는데..

 

7,8,9가 이미 0,1,2번 인덱스에 쓰였기 때문에 3번 인덱스에 7,8,9를 가져다 쓴다면...

 

6 8 7 9 5 4 3 2 1로 6보다 앞에 있는 수가 작아졌으므로 이전 순열이 된다.

 

즉 어떤 인덱스 i에서 a[i]보다 큰 수가 i+1,i+2,...,n-1 인덱스에 존재해야한다.

 

그러므로 뒤에서부터 순열을 읽어가면서, 오름차순으로 증가하다가 갑자기 작아지는 수를 발견한다면 그것을 pivot으로 삼는다.

 

 

 

위 그림에서 a[i-1] < a[i]이므로, a[i-1]을 pivot으로 삼는다.

 

그리고 i번부터 i,i+1,i+2,..,n-1까지 다시 순회해서, a[i-1]보다 큰 수가 존재하는지 찾는다.

 

여기서 바로 다음 순열을 찾아야하기 때문에 a[i-1]보다 바로 한 단계 큰 수를 찾는다. 

 

그렇기 때문에 뒤에서부터 n-1,n-2,...,i까지 순회해서 처음으로 a[i-1]보다 큰 a[j]를 찾는다면...

 

그러한 a[j]와 a[i-1]을 swap한다.

 

 

 

이렇게 바꾼다고 끝이 아니다.

 

원래 a[i-1]보다 한단계 큰 수로 바꿔서 [1,2,3,a[i-1],...]까지는 바로 다음 순열로 결정했는데

 

아직 a[i-1] 이후인 a[i],a[i+1],...를 임의로 배치할 수 있게 된다.

 

9 8 6 3 4 7 5 2 1을 보자. 

 

뒤에서부터 1 2 5 7까지 증가하다가 4로 작아지므로 pivot은 4이다.

 

9 8 6 3 4 7 5 2 1에서 1 2 5 7까지 읽다가 4보다 처음으로 큰 수는 5이므로.. 4와 5를 뒤바꾼다.

 

그러면 9 8 6 3 5 7 4 2 1이다.

 

그러면 9 8 6 3 4 7 5 2 1의 다음 순열이 9 8 6 3 5 7 4 2 1인가?

 

실제로는 9 8 6 3 5 1 2 4 7로 9 8 6 3 5 7 4 2 1 보다 더 작은 순열이 있다. 

 

그러니까 9 8 6 3 5 ? ? ? ?에서 ? ? ? ?을 1,2,4,7 4개로 적절하게 배치해야한다.

 

당연히 바로 다음 순열은 1 2 4 7을 오름차순으로 배치하는게 적절하다. 

 

즉 9 8 6 3 5 7 4 2 1로 4와 5를 swap한 다음 pivot index 이후인 7 4 2 1을 오름차순으로 1 2 4 7로 바꾸면 바로 다음 순열이 된다.

 

#다음 순열 next permutation을 찾는 알고리즘
n = int(input())

A = list(map(int,input().split()))

find = False

#뒤에서부터 순서대로 읽어서 오름차순인지 확인
#a[n-1] < a[n-2] < a[n-3] < ...
#처음으로 뒤에서부터 오름차순이 깨지는 i번 인덱스를 찾는다.
for i in range(n-2,-1,-1):
    
    if A[i] < A[i+1]:
        
        find = True
        a = A[i] #pivot
        
        #pivot이후인 i+1,i+2,..,n-1중에서 pivot보다 처음으로 한단계 더 큰 원소를 찾는다
        #뒤에서부터 읽어서 처음으로 A[j] > A[i]인 j번을 찾고 둘을 swap한다
        for j in range(n-1,i,-1):
            
            if A[j] > a:
                
                A[i],A[j] = A[j],A[i]
                break
        
        #swap하고 나서 i+1~n-1번을 a[i+1] < a[i+2] < ... < a[n-1]로 정렬시킨다.
        #a[i+1] > a[i+2] > ... > a[n-1]이기 때문에
        #a[i+1] > a[n-1]
        #a[i+2] > a[n-2]
        #...로 서로 swap하기만 하면 된다.
        #i+1 ~ n-1

        l = n - (i + 1)

        if l % 2 == 0:
            
            l //= 2
            l -= 1
        
        else:
            
            l //= 2

        for j in range(i+1,i+1+l+1):
            
            #i+1 > n-1
            #i+2 > n-1-1
            #...
            A[j],A[n-1-(j-(i+1))] = A[n-1-(j-(i+1))],A[j]
        
        
        break
        
if find == False: #pivot을 찾지 못한 경우
    
    print(-1)

else:

    print(*A)

 

 

 

i+1번부터 n-1번까지를 오름차순으로 재정렬하는 코드를 단순하게

 

A[i+1:] = A[i+1:][::-1]로 쓸 수는 있다.

 

n = int(input())

A = list(map(int,input().split()))

find = False

for i in range(n-2,-1,-1):
    
    if A[i] < A[i+1]:
        
        find = True
        a = A[i]
        for j in range(n-1,i,-1):
            
            if A[j] > a:
                
                A[i],A[j] = A[j],A[i]
                break
        
        #i+1 ~ n-1

        A[i+1:] = A[i+1:][::-1]
        break

if find == False:
    
    print(-1)

else:

    print(*A)

 

 

3. 문제2

 

10973번: 이전 순열 (acmicpc.net)

10973번: 이전 순열

 

 

4. 풀이

 

위 알고리즘을 이해했다면 주어진 순열의 바로 이전 순열 prev_permutation도 구현할 수 있다.

 

1 2 3 4 5 순열의 이전 순열은 존재하지 않기 때문에..

 

뒤에서부터 숫자를 5,4,3,2,1 읽어가면서 내림차순인지 확인한다.

 

이제 처음으로 내림차순이 깨지는 지점 i번 인덱스를 찾는다.

 

이전 순열을 찾아야하기 때문에 i+1번부터 n-1번 중에 처음으로 한단계 pivot보다 더 작은 원소 a[j]를 찾고

 

a[i]와 a[j]를 swap한다.

 

현재 a[i+1] < a[i+2] < a[i+3] < ... a[n-1]이므로.. 이를 반대로 내림차순 정렬

 

a[i+1] > a[i+2] > ... > a[n-1]로 정렬하면 바로 이전 순열이 된다.

 

 

#주어진 순열의 바로 이전 순열 prev_permutation을 구하는 알고리즘

n = int(input())

A = list(map(int,input().split()))

find = False

#수를 뒤에서부터 읽어가면서 처음으로 내림차순이 깨지는 지점을 찾는다.
#a[n-1] > a[n-2] > a[n-3] > ... a[i+1] < a[i]
for i in range(n-2,-1,-1):

    if A[i] > A[i+1]:

        a = A[i] #처음으로 내림차순이 깨지는 i번을 pivot으로 삼는다
        
        #i+1~n-1 구간에서 뒤에서부터 읽어서 pivot보다 처음으로 한단계 작은 수를 찾는다
        #그러한 수가 a[j]이면 a[i]와 swap
        for j in range(n-1,i,-1):
            
            if a > A[j]:
                
                A[i],A[j] = A[j],A[i]
                break
        
        #이제 i+1 ~ n-1 구간을 내림차순으로 정렬
        #a[i+1] > a[i+2] > ... a[n-1]로 하면 바로 이전 순열이 된다.
        A[i+1:] = A[i+1:][::-1]
        
        """
        l = n - (i+1)

        if l % 2 == 0:
            
            l //= 2
            l -= 1
        
        else:
            
            l //= 2

        for j in range(i+1,i+1+l+1):
            
            A[j],A[n-1-j+(i+1)] = A[n-1-j+(i+1)],A[j]"""

        find = True
        break

if find:

    print(*A)

else: #pivot을 찾지 못하는 경우

    print(-1)