[ BOJ ][JAVA][5568] 카드 놓기

www.acmicpc.net/problem/5568

5568번: 카드 놓기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2478	1330	1045	52.725%

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

예제 입력 1

4
2
1
2
12
1

예제 출력 1

7

코드

/*
    처음 풀때는 List를 이용해서 list.contains() 를 활용해 중복키를 체크하였다.
    하지만, HashSet을 이용하면 객체를 중복해서 저장할 수 없는 성질 덕분에 더 쉽게 구현할 수 있다. + 효율성이 아주 많이 개선된다.
    하지만 Set은 저장 순서가 유지되지 않기 때문에 저장 순서를 유지해야 한다면 LinkedHashSet을 사용해야 한다.
    또한 TreeMap과 마찬가지로 TreeSet은 키를 기준으로 자동으로 정렬을 해주는 성질이 있다.
    이처럼 Set의 큰 장점은 중복을 자동으로 제거해준다는 것이기 떄문에 잘 활용해보자.
*/
import java.io.*;
import java.util.*;
public class p5568 {
    static int n, k;
    static int[] arr, result;
    static boolean[] visit;
    static Set<String> set;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        set = new HashSet<>();
        visit = new boolean[n];
        result = new int[n];
        comb(0, 0);
        System.out.println(set.size());
    }
    static void comb(int start, int depth) {
        if (depth == k) {
            String str = "";
            for (int i = 0; i < k; i++) {
                str += result[i];
            }
            set.add(str);
            return; 
        }

        for (int i = 0; i < n; i++) {
            if (visit[i]) continue;
            visit[i] = true;
            result[depth] = arr[i];
            comb(start, depth + 1);
            visit[i] = false;
        }
    }
}

dfs 풀이

import java.io.*;
import java.util.*;
public class Main {
    public static StringTokenizer stk;
    public static StringBuffer sb = new StringBuffer();
    public static HashSet<String> hs = new HashSet<>();
    public static boolean[] visited;
    public static String[] card;
    public static int cnt = 0, n, k;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        card = new String[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            card[i] = br.readLine();
        }
        dfs(k, 1, "");
        System.out.println(hs.size());
    }
    public static void dfs(int k, int idx, String s) {
        if (k == 0) {
            hs.add(s);
            return;
        }
        if (idx > n) {
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(k - 1, i, s + card[i]);
                visited[i] = false;
            }
        }
    }
}