[JAVA]백준 5568번: 카드 놓기

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

5568번: 카드 놓기

1. 문제 설명

 

문제

• 카드 n(4 <=n <=10) 장 중에서 k(2 <=k <=4) 장을 선택해서 정수를 만들 것이다.
• 카드에는 1 이상 99 이하의 정수가 적혀있다.

출력

• n 장의 카드 중 k개를 선택해서 만들 수 있는 정수의 개수 출력

 

2. 풀이

 

카드를 선택해 만들 수 있는 정수가 중복될 수 있으므로 Set 자료구조를 사용해야 한다.

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

 

dfs 방식을 사용해 정수를 만들어 가고, set에 저장.

set의 크기를 출력하면 된다.

 

 

3. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;

public class Main {

    public static int cardNum, choiceNum;
    public static boolean[] visited;
    public static int[] list;
    public static Set<String> set = new HashSet<>();

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));



        cardNum = Integer.parseInt(br.readLine());
        choiceNum = Integer.parseInt(br.readLine());


        list = new int[cardNum];
        visited = new boolean[cardNum];

        for (int x = 0; x < cardNum; x++) {
            list[x] = Integer.parseInt(br.readLine());
        }

        canMakeNum(0, "");

        bw.write(String.valueOf(set.size()));
        bw.flush();


    }

    
    public static void canMakeNum(int choiceIdx, String num){
        if (choiceIdx == choiceNum) {
            set.add(num);
            return;
        }

        for (int x = 0; x < cardNum; x++) {
            if (!visited[x]) {
                visited[x] = true;
                canMakeNum(choiceIdx+1, num + list[x]);
                visited[x] = false;
            }
        }
    }


}