자바(백준) 5568 카드 놓기

오답 노트 & 새로 알게 된 점

문제를 보고 순열을 사용하여, 가능한 경우의 수를 모두 뽑은 뒤에, Set을 사용하여 중복된 것을 제외시키면 되겠다는 생각이 들었다. 그래서 재귀를 이용하여 순열을 사용( perm 메소드 ) 하고, set의 size를 구하여 출력시키면 AC이다.

 

---

 

코드

package BruteForce_Search;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    static Set<String> set;
    static String arr[];
    static boolean visit[];
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = atoi(st.nextToken()); //카드 갯수
 
        st = new StringTokenizer(br.readLine());
 
        int k = atoi(st.nextToken()); //뽑는 갯수
 
        set = new HashSet<>();
        arr = new String[n];
        visit = new boolean[n];
 
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = st.nextToken();
        }
 
        perm("", k, 0);
 
        System.out.print(set.size());
 
    }
    //순열을 사용
    static void perm(String str, int pick, int count){
        if(count == pick){
            set.add(str);
            return;
        }
        for(int i = 0; i < arr.length; i++){
            if(visit[i]) continue;
 
            visit[i] = true;
            perm(str + arr[i], pick, count + 1);
            visit[i] = false;
        }
    }
}