[백준/BOJ] 2992번 크면서 작은 수 (자바/Java)

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

2992번: 크면서 작은 수

---

1. 문제

정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다.

수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 같다. 하지만, 123과 432는 구성이 같지 않다

입력

첫째 줄에 X가 주어진다. (1 ≤ X ≤ 999999) X는 0으로 시작하지 않는다.

출력

첫째 줄에 결과를 출력한다. 만약 그러한 숫자가 없는 경우에는 0을 출력한다.

예제 입력 1 

156

예제 출력 1 

165

예제 입력 2 

330

예제 출력 2 

0

예제 입력 3 

27711

예제 출력 3 

71127

 

2. 풀이

 

우선 수의 구성에 대해 다시 설명해보자면, 수를 이루고 있는 각 숫자들을 이용해서 입력된 수보다 큰 수 중 작은 수를 구하는 것입니다.

123이 input으로 들어왔다면

 

123, 132, 213, 231, 312, 321

 

총 6가지 경우의 수가 존재합니다. 여기서 입력된 값인 123보다 큰 수 중에서 가장 작은 값은 132인 것을 알 수 있습니다.

 

이 문제는 백트래킹을 이용해서 구현할 수 있습니다. 우선 여기서 중요한 것은, 1, 2, 3을 가지고 순열을 구성하는 것입니다. 앞선 글에서 백트래킹을 이용해서 조합을 구현한 적이 있습니다. 하지만 순열과 조합은 중복을 허락하느냐, 허락하지 않느냐고 약간 다르기 때문에 아래에 있는 코드를 참고하시면 됩니다.

 

단순히 모든 가능한 숫자의 조합을 구하여 판단한 것에 불과하지만, 이 문제에서의 핵심은 "순열을 구현할 줄 아느냐"인 것 같습니다.

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        String[] num = String.valueOf(input).split("");
        int input_len = num.length;
        LinkedList<Integer> res = new LinkedList<>();
        // 백트래킹을 통해서 res에 가능한 모든 조합의 수를 등록함.
        backTracking(num, new String[input_len], new boolean[input_len], 0, 0, input_len, res);

        int min = 1000000;
        for(int i=1; i<res.size(); i++){ // 자기 자신은 제외
            int x = res.get(i);
            if(x > input && min > x) min = x;
        }

        if(min == 1000000) System.out.println(0);
        else System.out.println(min);
    }
    static void backTracking(String arr[], String[] out, boolean visited[], int depth,
                             int start, int r, LinkedList<Integer> res){
        if(depth == r){ // 재귀 메서드의 중단 조건
            StringBuilder sb = new StringBuilder(); // string을 이어 붙이기 위해 StringBuilder 사용
            for(String num : out) sb.append(num);
            res.add(Integer.parseInt(sb.toString()));
            return;
        }

        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                out[depth] = arr[i];
                backTracking(arr, out, visited,depth+1, start+1, r, res);
                visited[i] = false;
            }
        }

    }
}

 

3. 결과

 

4. 총평

 - BackTraking을 이용한 조합과 순열의 구현을 목적에 맞게 자유자재로 구현할 수 있어야할 것 같다.