문제 탐색하기

입력 자료 정리

1. 입력자료 n과 k는 각각 카드의 개수와 뽑는 카드의 수이다
2. 이어서 들어오는 n개의 입력값은 각 카드의 숫자이다.

해결방법 추론

1. 뽑는 카드의 개수가 고정되어있다면 완전탐색으로 쉽게 해결할 수 있었을 것이다
2. 하지만 뽑는 개수가 k의 값에 따라 변동되므로 백트래킹을 선택하였다
3. 중복으로 뽑는 경우를 제거하기 위해 결과를 보관할 Set 자료구조를 선택하였다
4. 완성된 Set의 크기를 출력하면 정답이 될 것이다.

시간복잡도 계산

1. 시간복잡도는 백트래킹에서 각 깊이마다 순회하는 횟수와 뽑는 깊이이다
2. O(n^k)가 될 것이고 최악의 경우 10^4이므로, 시간제한안에 해결할 수 있다
3. 따라서 시간복잡도는 O(n^k)이다

코드 설계하기

입력값 상태 관리하기

1. 먼저 n과 k는 int형 변수로 관리한다
2. 백트래킹을 위한 입력자료를 보관하는 n 크기의 int형 변수를 선언한다
3. 결과를 관리하기 위한 String 타입의 Set 자료구조를 사용한다
4. 방문 배열을 선언하여, 같은 인덱스의 숫자를 선택하지 않도록 한다.

구현코드 설계

1. 백트래킹을 돌면서, 깊이를 증가시키고,
   파라미터의 문자열에 i번째 위치의 배열 값을 넣어준다
2. 미방문한 인덱스에 대해서만 백트래킹을 진행하며, 종료후에는 방문체크를 해제한다
3. depth가 k가 되었을 때, set에 완성된 문자열을 넣어주고 종료한다

출력값 설계

1. 완성한 set 자료구조의 크기를 출력하면 정답이 된다

정답 코드

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


public class Main {

    static Set<String> sets;
    static int[] arr;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sets = new HashSet<>();
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        arr = new int[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        backtracking(n,k,"", 0);

        bw.write(sets.size()+"");

        br.close();
        bw.close();
    }

    private static void backtracking(int n, int k, String s, int depth) {
        if(depth == k){
            sets.add(s);
            return;
        }

        for (int i = 0; i < n; i++) {
            if(!visited[i]){
                visited[i] = true;
                backtracking(n,k,s + arr[i],depth+1);
                visited[i] = false;
            }
        }

    }
}

문제 링크

5568번 - 카드 놓기