Baekjoon 9742. 순열 / Java

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

알고리즘 설명

1. 입력 처리:
   • 입력으로 주어지는 문자열과 위치를 읽습니다.
   • 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열과 위치는 공백으로 구분됩니다.
2. 순열 생성:
   • 재귀적으로 순열을 생성합니다. 문자열의 각 문자를 하나씩 사용하여 순열을 만듭니다.
   • 이미 사용된 문자는 visit 배열을 통해 추적합니다.
3. 순열 카운팅:
   • cnt가 문자열의 길이와 같으면, 현재까지 만든 문자는 완전한 순열이 됩니다.
   • 순열의 카운트를 증가시키고, 현재 카운트가 찾고자 하는 위치와 같으면 해당 순열을 결과로 저장합니다.
4. 출력:
   • 모든 테스트 케이스를 처리한 후, 결과를 출력합니다.
   • 해당 위치의 순열이 없는 경우 "No permutation"을 출력합니다.

package letsgo;

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

public class Main {
    public static int num, resnum; // num: 찾고자 하는 순열의 위치, resnum: 현재까지 생성된 순열의 수
    public static boolean[] visit; // 각 문자의 방문 여부를 저장하는 배열
    public static char[] chars; // 현재 생성 중인 순열을 저장하는 배열
    public static String res; // 결과 순열을 저장하는 문자열

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

        // 입력이 더 이상 없을 때까지 반복 처리
        while((line = br.readLine()) != null) {
            StringTokenizer st = new StringTokenizer(line);
            String str = st.nextToken(); // 문자열 입력
            num = Integer.parseInt(st.nextToken()); // 찾고자 하는 순열의 위치

            // 초기화
            resnum = 0;
            res = "No permutation";
            visit = new boolean[str.length()]; // 방문 여부 배열 초기화
            chars = new char[str.length()]; // 순열 저장 배열 초기화

            // 순열 생성 시작
            sol(str, 0);

            // 지정된 위치의 순열이 없는 경우 처리
            if (resnum < num) {
                res = "No permutation";
            }

            // 결과 출력
            System.out.println(str + " " + num + " = " + res);
        }
    }

    // 순열 생성 함수
    public static void sol(String str, int cnt) {
        // 모든 문자를 사용하여 순열을 완성한 경우
        if (cnt == str.length()) {
            resnum++; // 순열 카운트 증가
            if (resnum == num) { // 현재 카운트가 찾고자 하는 위치와 같은 경우
                res = new String(chars); // 결과 순열 저장
            }
            return;
        }

        // 각 문자를 순차적으로 사용하여 순열 생성
        for (int i = 0; i < str.length(); i++) {
            if (!visit[i]) { // 해당 문자가 아직 사용되지 않은 경우
                visit[i] = true; // 방문 표시
                chars[cnt] = str.charAt(i); // 현재 위치에 문자 저장
                sol(str, cnt + 1); // 다음 위치로 이동하여 순열 생성
                visit[i] = false; // 방문 표시 해제 (백트래킹)
            }
        }
    }
}