CodingTest # 21 Java 2798 (블랙잭) 문제 풀이

출처 핀터레스트

 

요즘은 회사도 바쁘고, 사이드도 진행하느라, 바쁘지만,

 

그동안 잊고 안 했던 코딩 테스트를 다시 해보려고 한다.

 

오랜만에 해보니 역시 살짝 감을 잃은 느낌이다.

 

https://st-lab.tistory.com/97

[백준] 2798번 : 블랙잭 - JAVA [자바]

 

스트렌져님의 블로그를 참고하였다.

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

public class Test2798 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

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

        // 배열에 숫자들을 넣어준다.
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //M에 가까운 숫자 조합 가져오기
        int result = getLargeNumCombinations(arr, N, M);
        System.out.print(result);
    }

    private static int getLargeNumCombinations(int[] arr, int N, int M) {
        // 결과
        int result = 0;

        for(int i = 0; i < N - 2; i++) {

            if(arr[i] > M) continue;

            for(int j = i + 1; j < N - 1; j++) {

                if(arr[i] + arr[j] > M) continue;

                for(int k = j + 1; k < N; k++) {

                    int sum = arr[i] + arr[j] + arr[k];

                    if(sum == M) {
                        result = sum;
                        return result;
                    }

                    if(result < sum && sum < M) {
                        result = sum;
                    }

                }

            }

        }
        return result;
    }
}

브루트 포스라는 카테고리의 문제 중 하나이다.

 

브루트 포스란 '난폭한' 이란 뜻으로 어떠한 값을 찾아내기 위해 

 

이것저것 대입해보는 방법을 말한다고 한다.

 

처음에는 효율적?으로 문제를 푸는데 집중을 하였다.

 

아래는 처음 풀었던 코드이다.

 

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

public class Main {

    static Integer[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        arr = new Integer[N];

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

        // 배열에 숫자들을 넣어준다.
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //큰 숫자 순으로 정렬
        Arrays.sort(arr, Collections.reverseOrder());

        //M에 가까운 숫자 조합 가져오기
        int result = getLargeNumCombinations(M);
        System.out.print(result);
    }

    private static int getLargeNumCombinations(int max) {
        // 결과
        int result = 0;

        //제일 큰 두 값
        int most1;
        int most2;

        for(int j = 0; j < arr.length - 1; j++) {

            // 처음엔 제일 큰 두값이 0, 1 인덱스 지만,
            // 만약 큰 값을 발견하지 못하고 한 싸이클을 다시 돌게되면
            // 1씩 더해준다.
            most1 = arr[j];
            most2 = arr[j + 1];

            for(int i = j + 2; i < arr.length; i++) {
                // 셋이 합친값
                int sum = most1 + most2 + arr[i];

                //같거나 작으면 result return
                if(sum <= max) {
                    result = sum;
                    return result;
                }
            }

        }

        return result;
    }
}

 

이 코드의 문제점은

 

5, 3, 2, 1

 

아래의 반례로 인해 문제점이 들어났다.

 

나 같은 경우는 N값들을 받아 오름차순으로 정렬하고,

 

제일 큰 값 두 개를 먼저 더한 후 다 대입해보고

 

원하는 값이 나오지 않으면,

 

안되면 두 번째와 세 번째로 큰 값을 대입해보며

 

결국 마지막에 종료하는 코드였다.

 

하지만 돌이켜 보면, 모든 경우의 수는 나오지 않는 형식이었다.

 

무조건 큰 수를 더해서 차례로 뺀다 한들,

 

여러 조합들의 경우의 수를 다 구하진 못하는 것이었다.

 

브루트 포스, 말 그대로 모든 경우의 수를 대입해보는 방법으로 찾는 것이

 

정답이었다.