Baekjoon 10972 다음 순열 JAVA

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2010972

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 순열이 주어졌을 때 사전 순으로 다음으로 오는 순열을 구하는 문제다

만약 주어진 순열이 마지막이라면 -1을 출력한다.

 

해당 문제는 np라는 Next Permutation을 이용해서 해결했다.

예전에 배웠던 개념이긴 했으나 사용하지 않아 가물가물해서 다시 개념을 잡자는 생각으로

사용해 보았고, 사용법은 크게 어렵진 않다.

 

먼저 순열을 입력받아서 np를 호출할때 해당 순열을 파라미터로 같이 넘겨주고

1. 뒤쪽부터 탐색 교환위치(i-1) 찾기(i: 꼭대기)

2. 뒤쪽부터 탐색 교환 위치(i-1)와(i-1) 교환할 큰 값 위치(j) 찾기

3. 두 위치 값(i–1, j) 교환

4. 꼭대기 위치(i)부터 맨 뒤까지 오름차순 정렬

위와 같은 방식으로 동작하면서 만약 i값이 0이면 false(지금이 마지막 순열)

아닌 경우는 ture를 리턴해서 다음 순열 여부를 반환하는 방식으로 해결했다.