[백준] 16943. 숫자 재배치 -Java

사용한 자료구조 및 개념 : 순열

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ 순열을 이용하자.

2️⃣ A를 이용하여 C를 만들 때 문자열 그대로 가지고 다니자.

• 왜냐하면 0으로 시작하면 안 되는 C의 조건을 좀 더 쉽게 확인하기 위해 문자열 그대로 사용하였다.

👻 어려웠던 점

🚨처음에는 예제 2번을 이해하지 못했다. A가 1000, B가 5였는데 답이 -1이어서 "0001"도 있지 않나? 생각했다.

❗해결 : 문제를 잘 읽자!!! C는 0으로 시작되면 안 되기 때문에 1000만 될 수 있는데 1000은 5보다 크다. 따라서 조건을 만족하는 수가 없기 때문에 -1을 출력하는 것이었다.

Solution Code & 주석

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

public class Main {

    static String A;
    static int C, B, aLen;
    static boolean[] isSelected;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = st.nextToken();
        B = Integer.parseInt(st.nextToken());

        C = -1;
        aLen = A.length();
        isSelected = new boolean[aLen];

        perm("", 0);

        System.out.println(C);
    }

    private static void perm(String str, int cnt) {

        if (cnt == aLen) {
            int strToNum = Integer.parseInt(str);

            // 0으로 시작하지 않으면서 B보다 작은 경우에만 최댓값 갱신
            if (str.charAt(0) != '0' && strToNum < B) {
                C = Math.max(C, strToNum);
            }
            return;
        }

        for (int i = 0; i < aLen; i++) {
            if (isSelected[i])
                continue;
            isSelected[i] = true;
            perm(str + String.valueOf(A.charAt(i)), cnt + 1);
            isSelected[i] = false;
        }

    }

}

느낀 점

순열을 알고 있다면 그리 어려운 문제는 아니었다. 문제에 아예 대놓고 나와있기도 하고, 보자마자 순열을 이용하여 푸는 문제구나 바로 알아차릴 수 있었다. 내가 짠 코드가 그리 효율적이진 않은 것 같다. 특히, 냅다 재귀를 한 것, 문자열을 그대로 들고 다니면서 이어 붙이는 것이 시간, 공간적으로 효율적인가 의문이다.

제발 문제를 똑바로 읽자!! 금방 풀 수 있는 문제였는데 제대로 안 읽는 바람에 문제 이해하는 것에만 15분 정도 추가로 소비하였다.