Baekjoon (백준) 10972 번

💻 Beakjoon 10972 번 문제 -Java

• Baekjoon 10972 번

문제 설명

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) 중 순열 문제의 유형이다. 이 문제의 원리는
1. 입력 받은 숫자 배열을 뒤에서 부터 검색해서 오른차순이 아니기 되는 위치를 찾는다
2. 다시 뒤에서 부터 검색해서 첫번째 찾은 위치의 값보다 큰 값을 찾는다.
3. 서로 위치를 바꾼다.
4. 처음 찾은 위치 다음부터 끝가지 배열을 뒤집는다(revarse).
이 원리는 사전적으로 정의가 되어있기 때문에 가능하다고 한다. 이 원리가 왜 가능한지 궁금하신 분들은 다른 블로그에 잘 나와있으니 참고 하길 바란다,
말로 풀어서 설명하면 어려우니 코드를 보면서 이해보자.

문제 풀이

package Algorithm;

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

public class Baek_j_10972_result {
    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 nextPermutation(){
    
        /*뒤에서 부터 시작해서 첫 번쨰로 오름차순의 바뀌는 위치를 찾는다
        예를 들어 7 2 3 6 5 4 1의 경우의 3의 위치값을 찾는다
        */
        int i = input.length - 1;
        while(i > 0 && input[i-1] >= input[i]){
            i--;
        }

        //input가 마지막 순열 일때는 바로 false return
        if(i <= 0){
            return false;
        }

        /* 다시 뒤부터 input[i-1] 보다 작은 값을 찾는다.
        7 2 3 6 5 4 1 이 배열에서 위에서 찾은 값이 3이니 
        다시 뒤에서 부터 3보다 큰 값이 나오는 위치값 4를 찾는다.
        */
        int j = input.length - 1;
        while (input[i-1] >= input[j]){
            j--;
        }
        
        //그럼 i-1의 위치와 j의 위치 값을 바꾼다. -> 7 2 4 6 5 3 1
        swap(i-1,j);
        
        // i위치 부터 끝까지 배열을 뒤집는다
        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;
    }
}

💡 문제 해결 과정 느낌점

• 순열의 대한 이해도가 필요한 문제라고 느꼈다.

• 처음 이 문제를 접근할때 순열 문제라고 인지하지 못해 백트레킹을 통해 모든 경우의 수를 구하고 그 경우의 수 다음 인덱스 값을 출력하는 알고리즘으로 작성했는데 메모리 초과가 났다. 아래 코드가 내가 작성한 코드이다.

// 메모리 초과

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

public class Baek_j_10972 {
    static int N;
    static String input = "";
    static int sortArr[];
    static boolean vi[];
    static ArrayList result = new ArrayList<>();
    public static void main(String[] args) throws IOException{

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

        N = Integer.parseInt(br.readLine());
        sortArr = new int[N];
        vi = new boolean[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            input += st.nextToken();
            sortArr[i] = (input.charAt(i) - '0');
        }
        Arrays.sort(sortArr);
        dt(0,"");

        int index = 0;
        for(int i = 0; i < result.size(); i++){
            if(result.get(i).equals(input)){
                index = i+1;
                break;
            }
        }
        if(index == result.size()){
            System.out.println(-1);
        }
        else{
            String str = (String) result.get(index);
            for(int i = 0; i < N; i++){
                System.out.print(str.charAt(i) + " ");
            }
        }

    }

    public static void dt(int dep, String temp){
        if(N == dep){
            result.add(temp);
            return;
        }

        for(int i = 0 ; i < N; i++){
            if(!vi[i]){
                vi[i] = true;
                dt(dep+1, temp + Integer.toString(sortArr[i]));
                vi[i] = false;
            }
        }
    }
}