[백준 5568] 카드 놓기 (순열+Hash)

문제

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

5568번: 카드 놓기

 

 

알고리즘

Hash + 순열

 

 

풀이

1. 순열을 통해 카드를 선택할 수 있는 모든 경우의 수를 파악

2. 선택했던 카드를 또 선택하지 못하게 visit[] 배열을 통해 중복 체크

3. K개를 뽑았다면 Hash를 통해 만든 카드 경우의수를 체크

 

 

코드

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Test_Hash {
    static int N, K;
    static List<String> list;

    //뽑은 카드 체크
    static boolean[] visit;

    //만들 수 있는 카드
    static HashSet<String> card;

    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        K = Integer.parseInt(bf.readLine());
        list = new ArrayList<>();
        visit = new boolean[N];
        card = new HashSet<>();

        for (int i = 0; i < N; i++) {
            list.add((bf.readLine()));
        }
        pick(0, "");
        System.out.println(ans);
    }


    //카드를 K만큼 고른다. (순열)
    public static void pick(int cnt, String s) {
        if (cnt == K) {
            if(card.contains(s)) return;
            card.add(s);
            ans++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if(visit[i]) continue;
            visit[i] = true;
            pick(cnt + 1, s+list.get(i));
            visit[i] = false;
        }
    }
}