[Java] baekjoon_2798 : 블랙잭

브루트포스 알고리즘

블랙잭 : Bronze2

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

2798번: 블랙잭

 

 

 

첫 번째 작성한 코드

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    String[] str = br.readLine().split("\\s+");
    int[] num = new int[N];
    for (int i = 0; i < N; i++) {
      num[i] = Integer.parseInt(str[i]);
    }

    HashMap<Integer, Integer> hm = new HashMap<>();
    
    for (int i = 0; i < N; i++) {
      hm.put(i, M - num[i]);
    }
    
    List<Map.Entry<Integer, Integer>> el = new LinkedList<>(hm.entrySet());
    el.sort(Map.Entry.comparingByValue());
    
    
    int maxSum = 0;
    for (int i = 0; i < el.size() - 2; i++) {
      for (int j = i + 1; j < N - 1; j++) {
        for (int k = j + 1; k < N; k++) {
          int sum = 0;
          Map.Entry<Integer, Integer> entry = el.get(i);
          sum += num[entry.getKey()];
          entry = el.get(j);
          sum += num[entry.getKey()];
          entry = el.get(k);
          sum += num[entry.getKey()];

          if (sum <= M && sum >= maxSum) {
            maxSum = sum;
          }
        }
      }
    }
    
    bw.write(String.valueOf(maxSum));
    bw.newLine();
    bw.flush();
    bw.close();
  }
}

 

ㄴ HashMap 을 이용하였다.

ㄴ 하지만 HashMap을 이용하니 생각보다 코드가 복잡해져 코드 가독성이 떨어져 아래와 같이 리팩토링 하였다.

 

 

두 번째 작성한 코드

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // 입력 받기
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    int[] cards = new int[N];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      cards[i] = Integer.parseInt(st.nextToken());
    }

    int maxSum = 0;

    // 가능한 모든 카드 조합의 합 계산
    for (int i = 0; i < N - 2; i++) {
      for (int j = i + 1; j < N - 1; j++) {
        for (int k = j + 1; k < N; k++) {
          int sum = cards[i] + cards[j] + cards[k];

          // 주어진 M을 넘지 않으면서 최대한 가까운 합 갱신
          if (sum <= M && sum > maxSum) {
              maxSum = sum;
          }
        }
      }
    }

    // 결과 출력
    bw.write(String.valueOf(maxSum));
    bw.newLine();
    bw.flush();
    bw.close();
  }
}

 

ㄴ HashMap 을 이용하지 않고 일반 배열을 이용하여 일반 for문(3중 for문)으로도 카드 조합의 합을 계산할 수 있어 위와 같이 리팩토링 했다.

ㄴ 브루트포스(모든 경우를 탐색) 알고리즘을 사용하여 주어진 조건에 맞는 카드 조합을 찾고, 해당 조합의 합 중에서 M을 넘지 않으면서 최대한 가까운 합을 계산한다. 

ㄴ 각 카드에 적힌 숫자들을 cards라는 일반 배열에 저장하도록 했다.

ㄴ 변수 maxSum을 초기화하고, 가능한 모든 카드 조합의 합을 계산한다. (주어진 M을 넘지 않으면서 최대한 가까운 합 갱신)

 

 

브루트포스 알고리즘

brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "(정제되지 않은) 난폭한 힘, 폭력"이라는 뜻이다.

시간과 자원이 엄청나게 들어서 무식하다고 생각할 수도 있겠지만, 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장된다.

 

브루트포스 알고리즘(Exhaustive Search 또는 완전 탐색)은 가능한 모든 경우의 수를 나열하면서 원하는 조건에 맞는 해를 찾는 알고리즘이다. 이 알고리즘은 간단하고 직관적이지만, 경우의 수가 많을 때 효율성이 떨어질 수 있다.

브루트포스 알고리즘은 주로 작은 입력 크기에서 사용되거나, 다른 최적화 기법이 적용되기 어려운 경우에 활용된다. 경우의 수가 적을 때는 간편하게 적용할 수 있지만, 경우의 수가 크면 실행 시간이 급증하게 되므로 주의가 필요하다.

브루트포스의 구현은 중첩된 반복문을 사용하여 가능한 모든 조합을 검사하거나, 재귀적인 방법을 통해 모든 경우를 탐색하는 방식으로 이루어진다.

 

 

---

 

 

문제점 : HashMap 을 이용하였더니 코드 가독성이 떨어지는 것을 알 수 있었다.

해결 방법 : 코드 가독성을 높이기 위해 HashMap 대신 일반 배열을 이용하고 3중 for 문을 통해 문제를 풀 수 있었다.

깨달은 바 : 문제를 너무 어렵게만 생각하지 않아야겠다. 더 쉬운 방법이 있을 수 있으므로 많이 생각해봐야겠다.