[백준] 5568 카드 놓기 - Java

문제 - 카드 놓기

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

 

 

 

접근 방법

 

- 이 문제는 dfs 문제이다 dfs 방식으로 정수를 만든다

- 자료구조는 set를 사용할 것이다 이유는 dfs방식으로 정수를 만든것을 set 자료구조에 저장할 것인데 set의 특성상 중복 된 것을 처리해줄 수 있기 때문이다 

- 다른 자료구조를 사용할 경우 중복을 추가적으로 제거해줘야 하는 불편함이 있다

 

---

코드 작성

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static int n;
    static int k;
    static boolean[] visited;
    static int[] cardList;
    static Set<String> hashSet = new HashSet<>();

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

            n = Integer.parseInt(br.readLine());
            k = Integer.parseInt(br.readLine());

            cardList = new int[n];
            visited = new boolean[n];

            for (int i = 0; i < n; i++) {
                cardList[i] = Integer.parseInt(br.readLine());
            }

            makeNumber(0, "");

            System.out.println(hashSet.size());
        }


    }

    public static void makeNumber(int choiceIdx, String num) {
        if (choiceIdx == k) {
            hashSet.add(num);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                makeNumber(choiceIdx + 1, num + cardList[i]);
                visited[i] = false;
            }
        }
    }
}