백준 JAVA 5568 카드 놓기 리뷰

문제풀이

1. 카드 n(4 ≤ n ≤ 10)장, 각 카드에는 1이상 99이하의 정수가 적혀져있음,  이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택한다고 했다. 최대 10C4번만 보면 된다. 따라서 모든 경우를 보면 된다.

2.카드에 1이상 99이하의 정수가 적혀져있다고 했으니 087 이런식으로 앞에 '0'이 오는 경우는 고려할 필요가 없다.

3.카드가 10장 있고 모두 99가 적혀져 있다면 최대로 나올 수 있는 정수는 99가 10번 주어진 경우다. int, long 타입으로는 표현이 불가능하다. 서로 다른 수열의 나열만 파악하면 되므로 String 타입으로 수를 나열하면 된다.

4.중복확인 -> HashSet 이용해서 거르기

HashSet<String> list = new HashSet<>();

5.k가 정해져있지 않으니까 카드를 몇장 뽑을지는 때마다 다르다-> 재귀함수로 계속해서 호출

:재귀함수 종료조건은 카드를 k만큼 뽑았을때

6.하나의 카드를 여러번 사용하지 않기 위해서 visited 배열을 사용해서 카드방문을 체크한다.

7.dfs 종료 후 다른 dfs의 for문을 돌 때 방문배열 true한게 있으면 제대로 카드 방문을 하지 못하니까

dfs 호출 후 visited false 한다. 재귀 끝난후 false 하게

 

출처

import java.util.*;

public class Main{
    static int n,k;
    static HashSet<String> check =new HashSet<>();
    static int[] arr;
    static boolean[] visited;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n=scan.nextInt();
        k=scan.nextInt();

        arr=new int[n]; //카드 담아놓을 배열
        visited=new boolean[n];

        for(int i=0;i<n;i++){
            arr[i]=scan.nextInt();
        }

        dfs(0,"");
        System.out.println(check.size());
    }
    static void dfs(int cnt, String str){
        if(cnt==k) {
            check.add(str);
            return;
        }
        for(int i=0;i<n;i++){
            if(visited[i]) continue;
            visited[i]=true;
            dfs(cnt+1,str+arr[i]);
            visited[i]=false;
        }
    }

}