10972번 다음 순열 백준

문제:www.acmicpc.net/problem/10972

10972번: 다음 순열

이 문제는 N과M에서 했던 것을 이용하여 풀면 시간초과나는 것이 확정이기 때문에 그 방법으로 안 풀었다.

그렇다고 어떻게 풀어야 할 지 몰라서 결국 다른 분들이 어떻게 풀었나 찾아보았다.

 

풀이법은 이 블로그를 통해 봤다.

참고: fieldanimal.tistory.com/24

백준 10972 다음 순열

코드는 백준 맞은 사람 python3 중에 랭킹 1등에 해당하는 코딩을 봤다.

 

import sys
n = int(sys.stdin.readline())
seq = sys.stdin.readline().rstrip().split(' ')
seq = [int(x) for x in seq]
end = 0
findPoint = False
for i in range(len(seq)-1, 0, -1):
    if seq[i-1] < seq[i]:
        end = i-1
        findPoint = True
        break
if findPoint == True:
    for j in range(len(seq)-1, end, -1):
        if seq[end] < seq[j]:
            seq[j], seq[end] = seq[end], seq[j]
            break
    seq = seq[:end+1] + seq[len(seq)+1:end:-1]
    sys.stdout.write(' '.join(map(str,seq))+'\n')
else:
    print(-1)

첫번째로 처음부터 끝까지 다 내림차순이면 마지막이므로 findPoint를 False상태 그대로 두고 그렇지 않다면 True로 바꾼다음 if문에서 다음 순열을 찾는다.

end는 오른쪽에서 왼쪽까지 가는데 더이상 내림차순이 아닌 숫자인 것을 의미한다.

다음 순열 찾는 for문에서 end에 위치에 있는 값보다 크면서 가장 가까운 값을 찾는다. 그런다음 swap을 하고나서 end에 위치까지는 그대로 두고 그 뒤에 있는 숫자들은 역순으로 돌린다. 그러면 정답이 나온다.