[백준] 5568번: 카드 놓기 (Java)

1. 문제설명

각 카드에 1이상 99 이하의 정수가 적혀져 있고, 상근이는 n장(4 ≤ n ≤10)장을 가지고 있다.

그 중에서 k개를 선택해서 카드를 조합하여 만들 수 있는 정수의 개수를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 256M

 

2. 접근 방식

• 조합된 값 저장 시 중복된 값이 저장되지 않도록 HashSet을 사용한다.
• 백트래킹 방법을 하여 가능한 정수 조합을 탐색한다.
  • 현재 카드를 고른적이 있는지 방문 체크한다. (visited[현재위치]가 alse인지)
  • 고른 카드 수(count)를 1 증가시키고, 현재까지 만들어진 조합에 현재 카드를 추가해서 재귀 호출한다.
  • 만약 현재 고른 카드 수(count)가 k이면 현재 조합을 HastSet 추가하고 리턴한다.
  • 리턴된 다음에는 방문 처리를 취소한다. (백트래킹)

 

3. 최종 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, k;
    static String[] arr;
    static boolean[] visited;
    static StringBuilder st = new StringBuilder();
    static HashSet<String> set = new HashSet<>();

    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 String[n]; // 카드 배열 초기화
        visited = new boolean[n]; // 방문 체크 배열 초기화
        for(int i=0; i<n; i++) {
            arr[i] = br.readLine(); // 각 카드 수를 문자열로 저장
        }

        backTrack(0, ""); // 백트래킹 시작
        System.out.println(set.size()); // set의 size가 중복 제거된 조합의 수
    }

    static void backTrack(int count, String next) {
        if(count == k) { // 현재 선택한 카드 수가 k개이면
            set.add(next); // 현재 조합을 HastSet에 추가
            return;
        }

        for(int i=0; i<n; i++) { // 모든 카드를 탐색
            if(!visited[i]) { // 아직 선택하지 않은 카드이면
                visited[i] = true; // 해당 카드 방문 처리
                // {선택 카드 수 + 1}, {현재 카드 추가한 조합} 으로 재귀 호출
                backTrack(count+1, next+arr[i]);
                visited[i] = false; // 해당 카드 방문 처리 취소
            }
        }
    }
}

 

4. 시간복잡도

N개의 카드 중 K개를 선택하는 것으로 순열(Permutation)이 된다.

N개 중 K개를 선택하는 순열의 수는 $N! / (N-K)!$ 이다.

따라서 시간복잡도는 $O(N! / (N-K)!)$ 이 된다.