백준 2992번 : 크면서 작은 수

문제

---

2992번: 크면서 작은 수 (acmicpc.net)

2992번: 크면서 작은 수

 

아이디어

---

1. case를 분류해서 조건식으로만 푸는 방법

• 각 자리수를 index 취급
• 숫자가 모두 내림차순으로 정렬되어있으면, 더 커질 수 없으므로 0출력
• 숫자 중에 오름차순으로 정렬된게 있는지 확인, 이는 숫자의 순서를 바꿈으로써 커질 수 있는 위치를 뜻함
• 오름차순이 발견된 idx 중에서 가장 뒤에 있는 idx를 찾기 = point로 저장
• point 뒤에 있는 수 중에서 point 해당하는 수보다 크면서 가장 작은 수 구해서 swap
• swap 하면 그 자리엔 원래 수보다 큰 수가 오게 되므로 이후의 수는 모두 오름차순으로 정렬
• e.g 1234 => 1243 | 6372 => 6732 | 10044 => 10404 | 27711 => 71127

package biggerSmallest;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split("");
        int[] num = new int[s.length];
        for (int i = 0; i <s.length ; i++) {
            num[i] = Integer.parseInt(s[i]);
        }

        // 오름차순이 일어나는 idx 중 가장 마지막 idx를 확인하는 부분
        int point = -1;
        for (int i = 0; i < num.length-1; i++) {
            if(num[i]<num[i+1]){ // 오름차순 발견되었으면 인덱스 갱신
                point = i;
            }
        }
        // System.out.println("point는 " + point);

        int min = 0;
        int minIdx = -1;
        if(point==-1){ // 오름차순이 없는 경우
            System.out.println(0);
        } else {
            // 오름차순이 있는 경우
            // point뒤에 있는 수 중에서 point의 수보다 더 크면서 가장 작은 것 찾기
            for (int i = point+1; i < num.length; i++) {
                if(num[i]>num[point]){
                    if(minIdx==-1){
                        min = num[i];
                        minIdx = i;
                    } else{
                        if(num[i]<min){ // 같으면 더 앞에 있는 것과 바꾸는게 더 숫자가 작아지므로 idx 갱신안함
                            min = num[i];
                            minIdx = i;
                        }
                    }
                }
            }

            // swap
            int t = num[minIdx];
            num[minIdx] = num[point];
            num[point] = t;

            // bubble sort
            for (int i = point+1; i < num.length-1; i++) {
                for (int j = i+1; j < num.length; j++) {
                    if(num[i]>num[j]){
                        int p = num[i];
                        num[i] = num[j];
                        num[j] = p;
                    }
                }
            }

            // print
            for (int i = 0; i < num.length; i++) {
                System.out.print(num[i]);
            }
        }
    }
}

 

2. 순열을 이용해서 푸는 방법

• 순열을 이용해서 주어진 숫자의 조합으로 만들 수 있는 모든 순서쌍을 구함
• dept == r 을 만족하여 하나의 순서쌍을 구하는게 종료되면 조건문을 통과하도록 함
• 조건문 : 원래 값보다 큰 것 중에서 가장 작은 것
• 전역변수로 min을 만들어줘서 재귀함수 안에서 하나의 공통된 min 값을 사용할 수 있게 함

package biggerSmallestByPermutation;

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

public class Main {
    static int N, origin, min = Integer.MAX_VALUE;
    static int[] arr, out;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        // 입력 처리 : String -> int[]
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        origin = Integer.parseInt(s);
        String[] sarr = s.split("");
        arr = new int[sarr.length];
        for(int i=0; i<sarr.length; i++){
            arr[i] = Integer.parseInt(sarr[i]);
        }

        N = arr.length;
        out = new int[N];
        visited = new boolean[N];

        per(0);
        System.out.println(min == Integer.MAX_VALUE ? 0 : min);
    }

    public static void per(int dept){
        if(dept == N){
            // 배열을 int로 바꾸기
            int outNum = 0;
            for(int i=0; i<arr.length; i++){
                outNum += Math.pow(10,i)*out[i];

            }

            // 기존 수보다 더 크면서 가장 작은 min 구하기
            if(outNum>origin){
                if(outNum<min){
                    min=outNum;
                }
            }
            return;
        }

        for(int i=0; i<N; i++){
            if(visited[i]==false){
                visited[i]=true;
                out[dept] = arr[i];
                per(dept+1);
                visited[i]=false;
            }
        }
    }
}