[백준 10972] 다음 순열

1. 문제

www.acmicpc.net/problem/10972

10972번: 다음 순열

2. 접근 방법

순서를 어떻게 잡아야할까 하다가 서치를 조금 했다.

C++은 next permutation이라는게 있다고 한다.

(codedrive.tistory.com/386)

[BOJ]10972. 다음 순열

알고리즘 로직은 이대로 진행했다.

 

나는 처음에 가장 마지막에 오는 순열은 먼저 정리했다.

그리고 나서 마지막에 오는 순열이 아닐 경우에는 -> 무조건 다음 순열이 있을거니까 

비슷한 로직으로 진행했따.

1. 뒤에서부터 순열 비교해서 뒷 값이 앞 값보다 큰 경우를 찾아낸다.

2. 이 때, 뒷 값을 y라고 하고 앞 값을 x라고 한다.

3. 다시 뒤에서부터 확인하며 x값보다 큰 값이 있으면 그 값과 x값을 swap한다.

4. y에 해당하는 인덱스부터 sort를 해서 이어 붙인다.

3. 코드

python

def next():
    for i in range(len(numbers)-1, 0, -1):
        prev = numbers[i-1]
        now = numbers[i]
        if prev < now:
            for j in range(len(numbers)-1, i-1, -1):
                if numbers[j] > prev:
                    numbers[j], numbers[i-1] = numbers[i-1], numbers[j]
                    return i

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

if numbers == sorted(numbers, key=lambda x:-x):
    print(-1)
else:
    i = next()
    sort_numbers = sorted(numbers[i:])
    print(*numbers[:i], *sort_numbers, sep=" ")

4. 마치며

저기 링크에 있는 코드랑 비교하니 불리언 값으로 값을 비교해서 for문을 끝내도 됐겠구나 싶다.