[BOJ] 5568. 카드 놓기(조합).java

#. Problem

https://www.acmicpc.net/problem/5568

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

조합을 적용해야하는 문제이다.

N개의 카드 중 R개를 선택하여 만들 수 있는 정수의 개수 찾기!

#. Code v1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.Set;   public class BOJ5568_v2 {       static int N, K, card[];     static boolean visited[];     static Set<Integer> setNum;    // 중복 정수의 저장을 막기 위한 Set 자료형 사용       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());                  // init         visited = new boolean[11];         card = new int[N];         setNum = new HashSet<Integer>();                  for (int i = 0; i < N; i++)             card[i] = Integer.parseInt(br.readLine());           process(0, 0);         System.out.println(setNum.size());     }       // 문자열대신 정수를 사용한 방법     public static void process(int cnt, int num) {         // K 개수만큼 카드가 선택되었을 경우, Set에 add         if(cnt  == K) {             setNum.add(num);             return;         }         for (int i = 0; i < N; i++) {             // 이미 사용된 카드라면 pass             if(visited[i]) continue;             // 사용되지 않은 카드라면..             // 이 카드를 사용해볼까?             visited[i] = true;                              // 카드는 1이상 99이하라고 했다.             // 카드가 두 자리 숫자라면 기존 숫자에 100을 곱한 후 추가된 숫자를 더해주고             // 한 자리 숫자라면 기존 숫자에 10을 곱한 후 추가된 숫자를 더해주자.             int tmp;             if(card[i] > 9) tmp = num * 100 + card[i];             else tmp = num * 10 + card[i];             // 위 카드를 사용했으니까 cnt + 1 를 해주고 만들어진 숫자를 함께 재귀함수에 넘겨주기             process(cnt + 1, tmp);                          // 카드를 사용하지 않을래             visited[i] = false;             }     } }   Colored by Color Scripter

cs

 

#. Code v2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
 
public class BOJ5568_v1 {
 
    static int N, K, card[];
    static boolean visited[];
    static HashSet<String> setNum;    // 중복 저장을 막기 위한 Set 자료형 사용
 
    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());
        
        // init
        visited = new boolean[11];
        card = new int[N];
        setNum = new HashSet<String>();
        
        for (int i = 0; i < N; i++)
            card[i] = Integer.parseInt(br.readLine());
 
        process(0, "");
        System.out.println(setNum.size());
    }
 
    // 초기 StringBuilder를 사용해보았지만, 계속 string이 누적되어서
    // + operator 사용
    public static void process(int cnt, String str) {
        // K 개수만큼 카드가 선택되었을 경우, Set에 add
        if(cnt  == K) {
            setNum.add(str);
            return;
        }
        // 순서를 생각하면 안되므로 for문을 사용
        for (int i = 0; i < N; i++) {
            // 이미 사용된 카드라면 pass
            if(visited[i]) continue;
            // 카드를 사용해볼까?
            visited[i] = true;    
            // 카드를 사용했으니까 cnt를 늘려주고, str에 추가된 숫자를 붙여주자
            process(cnt + 1, str + Integer.toString(card[i]));
            // 카드를 사용하지 않을래
            visited[i] = false;    
        }
    }
}

Stringbuilder를 사용해서 해보려고 했지만,

계속 string이 누적되어버려서..

만일 사용한 카드에 적한 정수의 자릿수를 재귀함수에 같이 넘겨줘서

해당 카드를 사용하지 않을 경우 그 자릿수만큼 Stringbuilder에서 setLength() 함수를 활용해서 빼내면 되긴 할것 같다.

근데 정수 연산으로 해결하는 방법이 떠올라서 그냥 v1 방법으로 다시 해결했다.