[알고리즘 떠먹여 주는 남자] 백준 2798 - 블랙잭 for Node.js

안녕하세요!

 

두둥! 오늘의 마지막 알고리즘, 바로 블랙잭입니다. 이 문제는 백준 온라인 저지의 브루트포스 카테고리 안에 있는 문제입니다. 브루트포스 알고리즘에 대하여 아주 간단하게 설명을 드리자면, 무식하게 다 해보는 것입니다. 모든 경우의 수를 다 찾아보고 요구 조건에 맞는 결과값을 도출합니다. 따라서 시간 복잡도가 매우 높기 때문에 비싼 (비효율적인) 알고리즘이라고 할 수 있습니다. 하지만 브루트포스 알고리즘을 사용해서 문제를 해결해야 할 경우가 분명히 있으니 우리가 배우고 공부하는 것이겠죠..?

 

그럼 문제 풀이로 들어가 보겠습니다.

https://acmicpc.net/problem/2798 

2798번: 블랙잭

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1 복사

5 21
5 6 7 8 9

예제 출력 1 복사

21

예제 입력 2 복사

10 500
93 181 245 214 315 36 185 138 216 295

예제 출력 2 복사

497

 

문제 풀이

이 문제를 풀면서 어이없는 실수를 저질러 버렸습니다.. 때문에 이렇게 많이 틀려버렸네요 흑흑.. 아래에 코드 설명하면서 제가 어떤 삽질을 했는지 말씀 드리겠습니다.

위에서 말씀 드렸듯이 브루트포스는 모든 경우의 수를 다 따져보는 알고리즘입니다. 블랙잭은 세 장의 카드를 받고 그 세 카드의 합이 21을 넘지 않는 한에서 가장 큰 합을 가진 사람이 이기는 게임입니다. 이 문제는 변형 블랙잭입니다. 3장을 뽑는 룰은 동일하지만, 최대 숫자가 21이 아닌 딜러가 외치는 숫자 M 입니다.

 

제가 작성한 코드는 이렇습니다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const maxNumber = Number(input[0].split(' ')[1]);
const cards = input[1].split(' ').map(Number);

function playNewBlackjack(cards) {
  let closestSum = 0;
  for (let i = 0; i < cards.length - 2; i++) {
    for (let j = i + 1; j < cards.length - 1; j++) {
      for (let k = i + 2; k < cards.length; k++) {
        if (cards[i] !== cards[j] && cards[i] !== cards[k] && cards[j] !== cards[k]) {
          const currentCardsSetSum = cards[i] + cards[j] + cards[k];
          if (currentCardsSetSum <= maxNumber && currentCardsSetSum > closestSum) {
            closestSum = currentCardsSetSum;
          }
        }
        if (closestSum === maxNumber) return closestSum;
      }
    }
  }
  return closestSum
}

console.log(playNewBlackjack(cards));

playNewBlackjack 함수 안에 3중 포문 (nested for loops) 을 돌렸습니다. 각 포문 하나마다 카드 한장을 의미하며, 각 루프의 인덱스는

• i = 0
• j = i + 1
• k = i + 2

로 설정하였습니다. 그 이유는 만약 모든 루프의 인덱스 설정을 0부터 시작한다면 중복 카드가 선택 될 수 있기 때문입니다. 거기에다가, 가장 안쪽의 루프에서 또 한번 모든 카드가 겹치지 않을 때만 카드 모음의 최대값을 계산하도록 코드를 작성했습니다.

 

또한, 만약 이미 카드 셋의 합이 최대값과 동일할 경우 더 이상 큰 수가 나올 수 없기 때문에 바로 값을 리턴해 함수를 탈출하도록 해 줌으로써 불필요한 계산을 줄여주었습니다.

 

제가 했던 실수는 루프 안의 iteration 횟수 설정쪽이었는데, 간단하게 코드로 보여드리면 이랬습니다.

// 루프 iteration 횟수 설정 오류
for (let i = 0; i < cards.length - 3; i++) {
  for (let j = i + 1; j < cards.length - 2; j++) {
    for (let k = i + 2; k < cards.length - 1; k++) {
      // code......
    }
  }
}

결과적으로 모든 카드 셋을 다 체크하지 않게 되었던 것입니다. 이 실수를 한지도 모르고 엄한 부분 뒤져보느라 시간을 낭비했네요..ㅠ 어떤 일을 하든 항상 집중해서 하는 것이 중요하다는 것을 다시 한번 확인할 수 있었던 좋(지 않)은 경험이었습니다.

 

이렇게 브루트포스 알고리즘 문제를 처음으로 풀어보았습니다. 앞으로도 더 많은 알고리즘 문제를 풀어서 포스팅 할 수 있도록 하겠습니다. 또한 기본 개념에도 더욱 더 정진해서 한 단계 더 성장할 수 있는 개발자가 되어야겠습니다. 그럼 이번 포스트는 여기서 마무리 짓도록 하겠습니다. 모두 안녕~