Baekjoon (백준) 10973 번

💻 Beakjoon 10973 번 문제 -Java

• Baekjoon 10973 번

문제 설명

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

• 입력
  첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

• 출력
  첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

접근 방법

완전 탐색(Brute Force) 중 순열 문제의 유형이다. 10972번 문제와 거의 동일한데, 이 문제는 이번 순열을 찾으면 된다. 그래서 10972번을 토대로 반대로 찾는 방법으로 코드를 구현 하였다.

문제 풀이

package Algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek_j_10973 {
    static int input[];
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        input = new int[N];

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

        if(nextPermutation()){
            for(int var : input){
                System.out.print(var + " ");
            }
        }
        else System.out.println(-1);
    }

    static boolean prevPermutation(){
        int i = input.length-1;
        while(i > 0 && input[i-1] <= input[i]){
            i--;
        }

        if(i <= 0){
            return false;
        }

        int j = input.length-1;
        while(input[i-1] <= input[j]){
            j--;
        }

        swap(i-1,j);


        j = input.length-1;
        while(i < j){
            swap(i,j);
            i++;
            j--;
        }

        return true;
    }
    
    // 배열을 바꾸는 함수
    static int[] swap(int i,int j){
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;

        return input;
    }
}

💡 문제 해결 과정 느낌점

• 10972번과 같은 유형의 문제라 큰 어려움 없이 풀수 있었다.