[백준 2798번: 블랙잭](Java)

[알고리즘] 브루트포스(순열)

블랙잭 문제는 순열을 활용한 문제입니다.

Python에서는 itertools, C++에는 next_permutation와 같은 내장함수가 순열을 지원해 주시만,

Java에서는 내장함수가 없으므로 Recursion, 혹은 다중 for문을 활용하여 이를 직접 구현해야합니다.

 

아래 코드는 Recursion을 활용한 방법입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int CARD = 3;
    static int N, M;
    static int[] index;
    static boolean[] used;
    static int[] value;
    static int max;

    static void permutation(int cnt) {
        if (cnt == CARD) {
            int sum = 0;
            for (int i = 0; i < CARD; i++){
                sum += value[index[i]];
                if (sum > M) return;
            }
            if (sum > max) max = sum;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                used[i] = true;
                index[cnt] = i;
                permutation(cnt + 1);
                used[i] = false;
            }
        }
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        index = new int[N];
        used = new boolean[N];
        value = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) value[i] = Integer.parseInt(st.nextToken());
        permutation(0);
        System.out.println(max);
    }
}

 

 

알고리즘 문제를 푸는것도 아주 오랜만이었고, 특히 Java는 더욱 오랜만이었기 때문에, 기본적인 내용부터 정리해볼까 합니다.

 

1. 입출력 (I/O)

 

📌 입력

입력은 BufferedReader를 사용했습니다. 오랜만에 예전 제출 코드들을 보니 초반에는 Scanner를 사용했으나, 어느순간부터 BufferedReader를 사용하고 있더군요. Scanner는 공백을 경계로 값을 인식하기 때문에, 따로 가공을 할 필요가 없어서 편리하게 사용가능합니다. 반면, BufferedReader는 줄바꿈만을 인식하기 때문에 문자열 처리를 별도로 해주어야합니다.

 

📌 문자열 처리

문자열 처리에 대해 잠시 얘기해보겠습니다.

프로그래머스와 달리 백준의 경우 입출력 로직도 모두 개발자가 직접 작성해주어야 합니다. 따라서, 제공해주는 데이터가 어떤 형식으로 들어오는지, 어떤 형식으로 답안을 제출해야하는지 그 format을 잘 파악하는것이 중요합니다.

 

들어오는 데이터의 형식을 파악할 때는 몇 개의 데이터가, 어떻게 구분되어 들어오는지 확인해야합니다.

구분은 항상 공백문자(white space)를 활용합니다. 그러나 이때에 스페이스를 활용하는지 라인피드를 활용하는지 체크하여 입력값 처리를 해주어야 합니다. 쉽게말해 들어오는 데이터가 space로 구분되어 있는지, enter로 구분되어 있는지를 확인하는 것입니다.

 

저는 BufferedReader로 입력데이터의 줄 수만큼 readLine() 함수를 호출하고,

각 줄마다 space로 구분되어 있는 문자는 stringTokenizer를 활용하여 분리하는 방법을 주로 활용합니다.

아래 코드는 StringTokenizer 객체의 파라미터로, BufferdReader 객체로 입력받은 한 줄을 넘겨주는 코드입니다.

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

 

Java에서 delimiter를 기준으로 문자열을 분리하는데는 두 가지 방법이 있습니다.

String Class의 split() 메소드와, StringTokenizer를 활용하는 것입니다.

이 둘은 사용 방식과 성능에 있어서 차이를 가지는데, 이 부분에 대해서는 다음에 따로 정리하도록 하겠습니다.

 

📌 출력

위 입력부분에서 BufferedReader의 장점이 빠르다라고 했는데, 그 이유는 단어에서도 유추할 수 있듯 Buffer를 사용하기 때문입니다. BufferedReader의 자매품으로 출력에는 BufferedWriter 객체가 있습니다.

이는 출력의 기본코드인 System.out.println("")을 대체할 수 습니다.

 

해당 블랙잭 문제에서는 출력값이 단순히 정수 하나뿐이었기 때문에 System.out.println("")을 활용했지만, 출력해야할 데이터가 많은 문제에서는 BufferedWriter를 사용하는게 속도면에서 유리합니다.

 

 

 

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

2798번: 블랙잭