[BOJ] 백준 5568. 카드놓기

문제

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

5568번: 카드 놓기

---

풀이

순열과 Set 자료구조를 통해 해결했습니다. 

 

 우선 N개의 카드 중 K개의 카드를 순서를 고려하여 뽑아야하기 때문에, 순열 백트래킹을 통해 selected[] 배열에 인덱스를 저장합니다. 그리고 card[] 배열에 대입하여 해당하는 카드 번호들을 뽑아냅니다. 이때 번호의 나열은 StringBuilder를 이용해 합치고 그 결과를 Set에 집어넣습니다.

 

 Set은 중복을 허용하지 않는 자료구조입니다. 그렇기 때문에 Set의 size를 구하면 중복되지 않은 경우의 수가 나오게 됩니다.

 

 아래는 소스 코드입니다.

---

소스코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class B5568_카드놓기 {

    static int N,K;
    static int[] cards;
    static int[] selected;
    static boolean[] visited;
    static Set<String> set = new HashSet<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        cards = new int[N];
        visited = new boolean[N];
        selected = new int[N];
        for(int i = 0;i<N;i++){
            cards[i] = sc.nextInt();
        }
        perm(0);
        System.out.println(set.size());
    }

    static void perm(int idx){
        if(idx==K){
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i<K;i++) {
                sb.append(cards[selected[i]]);
            }
            set.add(sb.toString());
        }
        else{
            for(int i = 0;i<N;i++){
                if(!visited[i]){
                    visited[i] = true;
                    selected[idx] = i;
                    perm(idx+1);
                    visited[i] = false;
                }
            }
        }
    }
}