백준 5568 자바 - 카드 놓기 (BOJ 5568 JAVA)

문제 : boj5568

 

 

  우선 항상 문제를 풀 때, 그냥 무지성으로 모든 경우를 봐도 주어진 시간, 메모리 내에 가능한지부터 확인하는 습관을 들이는게 좋다. 이 문제의 경우엔 최대 10개 중 최대 4장을 선택하면 되므로, 최대 10C4번만 보면 된다. 따라서 그냥 모든 경우를 보면 된다!

-> 모든 경우를 확인하려면 k번의 반복문이 필요하다. 이렇게 반복문의 개수가 고정되지 않을 때는 재귀로 짜면 매우 편하다. 재귀를 쓰기 싫다면 스택을 쓰면 재귀로 짠 것과 동일하게 짤 수 있다.

 

  그럼 '만들 수 있는 정수'의 종류는 어떻게 알 수 있을까? 마찬가지로 제한 조건을 확인해보면서 생각해보면 된다. 우선 1부터 99까지의 정수이므로 0이 없어서, 숫자 앞에 0이 오는 경우는 무시해도 됨을 알 수 있다. 그리고 최대 99이므로 이 경우 최대로 나올 수 있는 정수는 99가 10번 주어진 경우이다. 그럼 10^21-1 까지 표현이 가능해야 한다. int는 물론이고 long으로도 표현이 불가한 숫자가 된다. 어차피 서로다른 수의 나열만 파악하면 되므로 그냥 String으로 다루면 될 것이다. 그리고 서로 다른 String의 가지수는 HashSet 등을 사용하면 쉽게 파악할 수 있다.

-> "1" + "23" = "123" !

 

  정리하자면, 완전탐색을 진행하여 모든 경우를 보면서 + k개의 문자가 합쳐진 경우 HashSet을 이용해 서로 다른 조합을 파악하면 된다. 완전탐색은 재귀로 진행 시 편리하다. 또한 하나의 카드를 여러번 사용할 수 없으므로, 방문배열을 두어 사용한 카드를 체크해줘야 한다.

-> 이 경우 N이 최대 10 이므로 비트마스킹을 통해서도 방문체크를 해볼 수 있다. 한번 해보는걸 추천. 코드는 둘 다 첨부했다.

 

 

  이하 다음의 테스트 케이스(예제 입력 1)에 대해 전체 과정을 그림으로 그려봤다.

4
2
1
2
12
1

 

 

 

코드 : github

 

[ 비트마스킹을 사용한 체크 ]

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

public class Main {
    private String[] arr;
    private int n, k, v;
    private HashSet<String> chk = new HashSet<>();

    private void bf(int cnt, String cur) {
        if (cnt == k) {
            chk.add(cur);
            return;
        }
        for (int i = 0; i < n; i++) {
            if ((v&1<<i)!=0) continue;
            v|=1<<i;
            bf(cnt+1, cur+arr[i]);
            v^=1<<i;
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        arr = new String[n];
        for (int i = 0; i < n; i++) arr[i] = br.readLine();

        bf(0, "");

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

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

[ 방문 배열을 통한 체크 ]

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

public class Main {
    private String[] arr;
    private int n, k;
    private HashSet<String> chk = new HashSet<>();
    private boolean[] v;

    private void bf(int cnt, String cur) {
        if (cnt == k) {
            chk.add(cur);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (v[i]) continue;
            v[i] = true;
            bf(cnt+1, cur+arr[i]);
            v[i] = false;
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        arr = new String[n];
        v = new boolean[n];
        for (int i = 0; i < n; i++) arr[i] = br.readLine();

        bf(0, "");

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

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}