백준 10972번 다음 순열 JAVA

링크텍스트

설명

c++에 next_permutation 함수가 있어서 실버3인 문제다. 자바로 풀면 이해하기 엄청 어렵다.
난 처음에 뒤에서 큰 거 하나만 바꾸면 되는 줄 알았다. 하지만 반례보니 아니었다.

1. 뒤에서부터 “오름차순이 깨지는 최초 지점”
   pivot (arr[i-1] < arr[i]) 을 찾는다.

사전순에서 다음이 되려면:
오른쪽 부분은 최대한 그대로 두고
왼쪽에서 가장 덜 증가하는 곳만 바꿔야 함

[ 앞부분 | 뒤쪽 내림차순 구간 ]
이 뒤쪽 내림차순 구간의 시작 바로 앞이 pivot이다.

핵심 개념
arr[i-1] < arr[i] 가 처음으로 성립하는 지점
그 전까지는 전부 사전순으로 더 큰 게 없음

왜 >= 인가
= 는 비증가 (내림차순 포함) 를 의미
이 구간 전체는 이미 가장 큰 배치
이 안에서 아무리 바꿔도 다음 순열 안 나옴

2. swap 대상 찾기
   arr[i-1] = pivot
   arr[i ... n-1] = 내림차순 구간
3. 뒤를 가장 작은 상태로 만든다.
   요약 : 가장 오른쪽에서 증가시킬 수 있는 최소 위치(pivot)를 찾고 →
   pivot보다 큰 최소값과 바꾸고 → 뒤를 가장 작은 상태로 만든다
   시간복잡도: O(N), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

    import java.io.*;
    import java.util.*;

    public class Main {

        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            int n = Integer.parseInt(br.readLine());

            int [] arr = new int[n];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            int i = n-1;
            while(i>0 && arr[i-1]>=arr[i]) i--;

            if(i==0){
                System.out.println(-1);
                return;
            }

            int j = n-1;
            while(arr[i-1]>=arr[j]) j--;

            int temp = arr[i-1];
            arr[i-1] = arr[j];
            arr[j] = temp;
            
            int left = i, right = n-1;
            while(left<right){
                temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }

            StringBuilder sb = new StringBuilder();
            for(int num : arr){
                sb.append(num).append(" ");
            }

            System.out.print(sb);
        }
    }