백준_9742_순열

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

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

public class Main{

    static int totalCount, N;
    static boolean isSelected[]; // 중복 방지 위해 방문했는지 체크하는 배열
    static char[] chars; // 문자를 담을 배열
    static String answer;

    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();
            N = Integer.parseInt(st.nextToken());

            totalCount = 0;
            chars = new char[str.length()];
            isSelected = new boolean[str.length()];

            dfs(str, 0); 

            if(totalCount < N) answer = "No permutation";
            
            System.out.println(str + " " + N + " = " + answer);
        }
    }

    static void dfs(String str, int cnt){ // cnt = 현재 크기 
    	
    	// 종료 조건 
        if(cnt==str.length()){ // 크기가 str과 같아지면 totalCount++ 
            totalCount++;
            
            if(totalCount == N) answer = new String(chars); // 문자배열 -> string 으로 변환

            return;
        }

        //확장 
        for(int i=0; i<str.length(); i++){ // 문자열 탐색 
        	
            if(!isSelected[i]){ // 방문 전 이라면 
                isSelected[i]=true;
                chars[cnt]=str.charAt(i); // 현재크기 = 현재위치에 i넣어줌 
                
                dfs(str, cnt+1); // 넣어줬으니까 cnt+1
                
                isSelected[i]=false; // 빠져나왔으니 false 
            }
        }
    }
}

1. 입력값의 크기가 주어지지 않는경우

• while((line=br.readLine())!=null) 을 사용하여 해결

2. DFS (깊이 우선 탐색)

• dfs에 인자로 오는 int 값은 현재 크기이다.

만약 사전순으로 입력이 주어지지 않는다면??

// 입력 문자열을 정렬
            char[] sortedChars = str.toCharArray();
            Arrays.sort(sortedChars);
            String sortedStr = new String(sortedChars);