다음 순열 풀이

문제 링크: https://www.acmicpc.net/problem/10972

백준  알고리즘 기초 2/2 520에서 1번째 - 10972번 다음 순열을 풀어보았다.

 

풀이: next permutation을 구하는 문제이다. 

파이썬은 https://dallae7.tistory.com/155 를 참고했다.

 

C++

 

Python

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

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

if not next_permutation():
    print(-1)
else:
    for i in range(N):
        print(arr[i], end=" ")

Java