[문제풀이] B9742 순열

순열

---

  🪅 매 반복마다, 다음 반복에 영향을 주지 않게 초기화를 잘 하였는가
  🪅 입력을 받지 못했을 때, NullPointException을 띄우지 않고 프로그램을 올바르게 종료시킬 수 있는가
  🪅 순열을 구현할 수 있는가

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

/**
 * 백준 9742번 순열
 * 입력:
 * 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 
 * 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 
 * 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다.
 * 
 * 출력:
 * 각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 
 * 만약, 해당하는 순열이 없는 경우에는 "No permutation"을 출력한다.
 */
public class Main {
    static char[] arr;
    static int th;
    static boolean[] isSelected;
    static int[] selection;
    static int cnt;
    public static void permutation(int r) {
        if(r == arr.length) {
            if(++cnt == th) {
                System.out.print(String.valueOf(arr) + " " + th + " = ");
                for(int i = 0; i < arr.length; i++) {
                    System.out.print(arr[selection[i]]);
                }
                System.out.println();
            }
            return;
        }
        for(int i = 0; i < arr.length; i++) {
            if(isSelected[i]) continue;
            isSelected[i] = true;
            selection[r] = i;
            permutation(r+1);
            isSelected[i] = false;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            String str = br.readLine();
            if(str == null ) break;
            StringTokenizer token = new StringTokenizer(str, " ");
            arr = token.nextToken().toCharArray();
            th = Integer.parseInt(token.nextToken());
            isSelected = new boolean[arr.length];
            selection = new int[arr.length];
            cnt = 0;
            permutation(0);
            if(th > cnt) {
                System.out.println(String.valueOf(arr) + " " + th +" = No permutation");
            }
        }
    }
}

💡 문제 접근 방법
제목이 순열이란 것을 빼놓고 생각했을 때,
문자의 순서가 결과에 영향을 미치므로 순열로 구현해야겠다고 생각했다.
다만, 주의해야했던 점은 입력이 없었을 때 (str = null) 제대로 끝내는 방법과
매 반복마다 초기화를 적절히 했는가(cnt = 0)가 이 문제를 풀 수 있느냐 없느냐의 포인트였다.