이번 문제는 프로그래머스의 레벨 3 n + 1 카드 게임 문제이다.
2024 KAKAO 인턴십 코딩테스트 문제였다.
지원 당시에는 문제를 풀지 못했었는데, 다시 한 번 풀어보려 한다.
문제를 차근차근 읽어보자.
최대 996장의 카드가 주어질 수 있다.
또한 동전 또한 996개 까지 주어질 수 있다.
게임이 시작되면, 처음에 6장의 카드를 가져가도록 한다.
이후 매 턴이 올 때마다 두 장의 카드를 뽑는데, 이 때 동전이 사용된다.
동전을 카드 장 수만큼 사용해서 카드를 가져갈 수가 있다.
이 때 최대한 라운드를 진행한다면, 몇 라운드까지 갈 수 있는가?
완전 탐색
아무래도 게임 이론에 관한 문제인 것 같다.
이 문제를 모든 경우에 대해 탐색해서 풀 수 있을까?
최악의 경우는 996장의 카드와 996개의 동전이 주어질 때이다.
두 장씩 뽑는데, 버리기, 왼쪽, 오른쪽, 모두의 4가지 경우를 선택할 수 있다.
첫 패인 332장을 제외하고, 2장씩 뽑으니 332장의 카드가 있는 것과 같다.
그 말인 즉, 332 ^ 4가지의 경우의 수가 나올 수 있다는 것이다.
이는 반드시 시간초과를 야기하기 때문에 옳은 풀이가 아니다.
Greedy?
이 문제를 그리디하게 풀 수 있는 방법은 없을까?
매 라운드에서 확인해야 할 것은 아래의 두 가지이다.
- 현재 패와 뽑은 두 장의 카드를 합쳐서
n + 1을 만들 수 있는가? - 패를 버렸을 때, 미래에 뽑을 카드에 대해 지장이 없는가?
2번의 조건은 예를 들어, 3 6 7 2를 첫 패로 가졌다고 생각해보자.
1 10의 패를 뽑으면 10 + 3을 통해 13을 만들 수 있다.
이 때 만약 1을 버린다면? 이후에 12를 뽑을 가능성을 배제한 것이다.
그럼 이후에 12가 나왔을 때 버틸 수 있는 한 턴을 버린 것과 같다.
또한, 가장 중요한 점은 우리에게 동전은 제한되어 있다는 것이다.
따라서 동전을 사용해서 패를 뽑는 데에는 아래와 같은 우선순위가 필요할 것 같다.
- 이미 패에 들어온 카드로
n + 1을 만들 수 있다면 낸다. - 패에 있는 카드와 합쳐
n + 1을 만들 수 있는 카드는 반드시 뽑는다. - 위의 두 경우 모두 만들 수 없다면, 두 장 모두 뽑는다.
위의 조건대로 한 번 구현해보자!
처음에는 아래와 같이 매 상황마다 패에 대해 판단하려 했다.
for (int i = cards.size() / 3; i < cards.size(); i += 2) {
// 남은 카드 두 장씩 훑는다
int left_draw = cards[i];
int right_draw = cards[i + 1];
// 1. 손에 있는 두 패로 n + 1을 만들 수 있는 경우
if (hands.size() >= 2) {
for (int i : hands) {
if (card_check[goal - i]) {
hands.erase(remove(hands.begin(), hands.end(), i), hands.end());
hands.erase(remove(hands.begin(), hands.end(), goal - i), hands.end());
answer++;
continue;
}
}
}
// 2. 손에 있는 패 1장, 뽑은 카드 1장으로 n + 1을 만들 수 있는 경우
else if (hands.size() >= 1 && coin >= 1) {
if (card_check[goal - left_draw]) {
hands.erase(remove(hands.begin(), hands.end(), left_draw), hands.end());
hands.erase(remove(hands.begin(), hands.end(), goal - left_draw), hands.end());
card_check[cards[left_draw]] = true;
answer++;
coin--;
continue;
}
if (card_check[goal - right_draw]) {
hands.erase(remove(hands.begin(), hands.end(), right_draw), hands.end());
hands.erase(remove(hands.begin(), hands.end(), goal - right_draw), hands.end());
card_check[cards[right_draw]] = true;
answer++;
coin--;
continue;
}
}
// 3. 손에 있는 패로는 만들 수 없는 경우
else if (coin >= 2) {
hands.push_back(left_draw);
hands.push_back(right_draw);
answer++;
coin -= 2;
continue;
}
else
break;
}하지만 도저히 해결이 되지를 않아, 결국 풀이를 참고했다.
놀라운 사실은, 굳이 패를 그때 그때 결정할 필요가 없다는 것이다.
앞에서부터 받은 패를 저장하며 누적해서 훑어도 상관이 없다는 말이다.
이유가 뭘까?
패를 누적 저장하는 대신, 이미 뽑은 카드까지의 조합을 매번 검증한다면?
미래에서 과거를 보고 결정하는 것과 같은 형태가 된다.
즉, 만들 수 있었던 조합을 미래에서 보고 코인을 사용하는 것이다.
만들 수 있었던 조합 조차 없다면, 게임을 끝내면 된다.
따라서, 최종적으로 아래와 같이 구현되었다.
bool card_check[1001];
bool validate_hand(vector<int> &hands, int goal) {
for (int card : hands) {
if (find(hands.begin(), hands.end(), goal - card) != hands.end()) {
hands.erase(remove(hands.begin(), hands.end(), card), hands.end());
hands.erase(remove(hands.begin(), hands.end(), goal - card), hands.end());
card_check[card] = 0;
card_check[goal - card] = 0;
return true;
}
}
return false;
}
bool validate_draw_one(vector<int>& hands, int goal) {
for (int card : hands) {
if (card_check[goal - card]) {
hands.erase(remove(hands.begin(), hands.end(), card), hands.end());
card_check[card] = 0;
card_check[goal - card] = 0;
return true;
}
}
return false;
}
bool validate_draw_two(int goal) {
for (int k = 1; k < goal; k++) {
if (card_check[k] && card_check[goal - k]) {
card_check[k] = 0;
card_check[goal - k] = 0;
return true;
}
}
return false;
}
int solution(int coin, vector<int> cards) {
int answer = 1, goal = cards.size() + 1;
vector<int> hands;
for (int i = 0; i < cards.size() / 3; i++) {
hands.push_back(cards[i]);
card_check[cards[i]] = true;
}
for (int i = cards.size() / 3; i < cards.size(); i += 2) {
// 남은 카드 두 장씩 훑는다
card_check[cards[i]] = true;
card_check[cards[i + 1]] = true;
// 1. 손에 있는 두 패로 n + 1을 만들 수 있는 경우
if (hands.size() >= 2 && validate_hand(hands, goal))
answer++;
// 2. 손에 있는 패 1장, 뽑은 카드 1장으로 n + 1을 만들 수 있는 경우
else if (hands.size() >= 1 && coin >= 1 && validate_draw_one(hands, goal)) {
answer++;
coin--;
}
// 3. 손에 있는 패를 모두 써야 만들 수 있는 경우
else if (coin >= 2 && validate_draw_two(goal)) {
answer++;
coin -= 2;
}
else
break;
}
return answer;
}시험을 칠 당시엔 긴장해서 그런지 머릿속이 하얬었다.
지금 다시 풀어봐도 못 푼 것은 마찬가지지만, 그 때 보단 나았다.
좀 더 열심히 연습하도록 하자.