[백준] 16943번 숫자 재배치 문제 풀어보기 : Programming Story

1. 문제

www.acmicpc.net/problem/16943

문제는 위 링크에 들어가면 확인할 수 있다.

2. 풀이

위 풀이에서 매번 순열을 하는 코드는 자바로 아래와 같이 구현할 수 있다.

 static boolean next_permutation(char[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

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

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

        char temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }

자바에서 순열을 만드는 코드이다.

또한 우리가 문자로 입력을 받았기 때문에 이를 다시 숫자로 돌리는 과정이 필요하다.

C++의 경우에는 위의 풀이처럼 stoi를 써야 하지만 자바는 이를 또 구현해주는 과정이 필요하다.

char 배열을 int로 바꿔주는 부분의 함수는 아래와 같다.

   static int toNum(char[] a) {
        int ans = 0;
        for (char ch : a) {
            ans = ans * 10 + (ch - '0');
        }
        return ans;
    }

따라서 매번 순열로 순서를 바꾸어주고 이를 다시 toNum 함수를 사용해서 숫자로 바꾸어주는 것이다. 그런 다음에 문제의 조건을 만족하는지 살펴보면 된다.

3. 코드

전체 코드는 아래와 같다.

import java.util.*;
public class Main {
    static boolean next_permutation(char[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

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

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

        char temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
    static int toNum(char[] a) {
        int ans = 0;
        for (char ch : a) {
            ans = ans * 10 + (ch - '0');
        }
        return ans;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.next().toCharArray();
        int b = sc.nextInt();
        Arrays.sort(a);
        int ans = -1;
        do {
            int number = toNum(a);
            if (a[0] != '0' && number < b) {
                if (ans == -1 || ans < number) {
                    ans = number;
                }
            }
        } while (next_permutation(a));
        System.out.println(ans);
    }
}