백준 5568 카드 놓기 문제풀이 (JAVA)

문제 링크

문제

상근이는 카드 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개 줄에는 카드에 적혀있는 수가 주어진다.

출력

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

풀이

카드를 뽑았을 때 모든 경우의 수를 전부 계산한다.
물론, 전부 계산하면 중복된 값이 발생하기 때문에 HashSet에다가 넣어주면 중복된 값은 입력되지 않는다!
재귀함수를 이용하여, 아직 뽑지 않았으면(if(!visited[i])) 한 장을 뽑고, 그 다음 번호부터 하나씩 뽑는다. 전부 다 뽑았으면(remain == 0) HashSet에 넣고 함수를 종료한다. 그리고, 함수를 나오면서, 상위 함수로 돌아가서 뽑은 흔적을 지워준다. 그래야만 뒤에 진행되는 반복문에서 그 카드를 나중에 뽑을 수 있다.

소스코드

import java.util.*;
import java.io.*;
public class Main{
    public static int NUMBER_OF_CARD;
    public static int NUMBER_OF_SELECT;
    public static String card[];
    public static boolean visited[];
    public static HashSet<String> hs = new HashSet<String>();
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
      
        NUMBER_OF_CARD  = Integer.parseInt(br.readLine());
        NUMBER_OF_SELECT = Integer.parseInt(br.readLine());
        card = new String [NUMBER_OF_CARD];
        for(int i=0;i<NUMBER_OF_CARD;i++) {
            card[i] = br.readLine();
        }
        visited = new boolean [NUMBER_OF_CARD];
        selectCard(NUMBER_OF_SELECT, "");
        
        sb.append(hs.size());
        sb.append("\n"); 
        
        bw.write(sb.toString());
        
        bw.flush();
        br.close();
        bw.close();
        
    }
    public static void selectCard(int remain, String k) {
        if(remain == 0) {
            hs.add(k);
            return;
        }
        for(int i=0;i<NUMBER_OF_CARD;i++) {
            if(!visited[i]) {
                visited[i] = true;
                selectCard(remain-1, k + card[i]);
                visited[i] = false;
            }
        }
        
    }

    
}