[백준] 10972번 > 다음 순열

www.acmicpc.net/problem/10972

10972번: 다음 순열

문제

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을 출력한다.

예제 입력 1

4

1 2 3 4

예제 출력 1

1 2 4 3

예제 입력 2

5

5 4 3 2 1

예제 출력 2

-1

 

 

---

풀이

 

import sys
input = sys.stdin.readline
n = int(input())
s = list(map(int, input().split()))
x = 0
for i in range(n - 1, 0, -1):
    if s[i - 1] < s[i]:
        x = i - 1
        break
for i in range(n - 1, 0, -1):
    if s[x] < s[i]:
        s[x], s[i] = s[i], s[x]
        s = s[:x + 1] + sorted(s[x + 1:])
        print(*s)
        exit()
print(-1)

C++의 next_permutation함수를 구현한 것이다. 

 

순열의 마지막이라는 뜻은 모든 원소가 오름차순으로 정렬되어 있다는 말

따라서 두번째 for문안의 if문으로 들어가지 않는다.

 

그외에는 맨 뒤부터 두개씩 검사한다.

[1,5,3,2] 가 있다면 (3, 2) , (5, 3) , (1, 5) 의 순으로 검사를하는데 뒤의 수가 더 큰것이 있다면 x에 그 앞 값을 저장하고 break를 통해 빠져나온다.

두번째 for문을 통해 x에 저장한 값과 맨 뒤부터 검사하여 더 큰값이 있다면 두 값을 SWAP해준다. ==> [2,5,3,1]

그 다음 x위치 뒤의 값을 정렬하여 붙혀준다 ==> [2,1,3,5]