[프로그래머스] 258707 n + 1 카드 게임 (javascript)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258707

풀이

최적해를 구하는 문제이다. 당연히 처음에는 완전 탐색부터 고려했다. 하지만 완전 탐색은 카드 2장에 대해 구매/미구매의 4가지 경우가 존재하므로, 경우의 수가 계속 4배씩 불어난다. 카드 수가 최대 1000장인 점을 생각하면, 경우의 수는 사실상 $4^{1000}$ 에 가까운 수준까지 커질 수 있다. 이는 2의 2000승(ㅋㅋ,,)이 넘는 연산량이므로, 완전 탐색으로는 절대 해결할 수 없는 문제였다.

이후 자연스럽게 그리디 알고리즘을 고려했는데, 지역 최적해가 전역 최적해를 보장하는지를 생각해보기도 전에, 애초에 지역 최적해조차 어떻게 구해야 할지부터 감이 잡히지 않았다.

그리고 나서 다른 방법과 알고리즘들을 생각해보다가 전혀 해결법이 떠오르지 않아 사실 풀이를 실패했다. 힌트로 이 문제가 그리디 알고리즘으로 풀린다는 것을 알게 되었고, 그 뒤에는 “어떤 방향의 그리디여야 성공할 수 있을까”만 계속 고민했다.

첫 번째 시도 때, 그리디한 방법을 떠올리지 못했던 이유가 나중에 보니 꽤 중요했다. 현실 세계에 너무 몰입한 나머지, 문제 안에 들어 있는 중요한 힌트를 놓치고 있었던 것이다.

현실 세계에서는 뒤에 나올 카드를 미리 알 수 없지만, 이 문제에서는 뒤에 나올 카드가 이미 전부 주어져 있다.

즉, 현재 선택이 미래에 어떤 의미를 갖는지 미리 계산할 수 있고, 그래서 그리디가 가능해진다.

우선 이미 짝이 맞춰진 카드는 진행할 수 있는 라운드를 자동으로 늘려준다. 이 부분은 사실 고민할 여지가 없다. 그리고 새로 나온 카드가 현재 손패의 어떤 카드와 바로 짝을 이룰 수 있다면, 이 카드는 동전 1개로 즉시 한 라운드를 버틸 수 있는 자원이 된다. 이 라운드에 구매하지 않는다면, 이후에 해당 비용보다 저렴한 비용으로 더 큰 이득을 볼 수 있는 경우가 절대 없기 때문에 무조건 구매하는 것이 최적임이 자명하다.

문제는 손에 있는 카드와 짝이 맞지 않는 새 카드들이다. 이 카드들은 지금 사야 할지 말아야 할지가 애매하다. 이번 라운드가 지나면 다시 구매할 수 없기 때문에 그냥 넘겨도 되는지 확신이 잘 서지 않는다. 그러나 미래의 카드 순서를 이미 알고 있으니, 손에 있는 카드들로 어디까지 진행할 수 있는지 계산할 수 있고, 그 시점이 오면 이전에 지나쳤던 카드들을 샀어야 했는지 아닌지도 판단할 수 있다.

이후 사건을 미리 알고, 시간을 되돌려 과거의 선택을 다시 판단하는 식의, 정말 떠올리기 어려운 풀이였다.

정답 코드

javascript

const solution = (coin, cards) => {
	const totalCards = cards.length;
	const initialHandSize = totalCards / 3;
	const maxRounds = totalCards / 3;

	const hand = new Set();
	const pending = new Set();
	const pendingPairCards = [];

	let availablePairCount = 0;

	const getPairCard = (card) => totalCards + 1 - card;

	const addPendingCard = (card) => {
		const pairCard = getPairCard(card);

		if (pending.has(pairCard)) {
			pendingPairCards.push(card);
		}

		pending.add(card);
	};

	const usePendingPair = () => {
		if (coin < 2) {
			return false;
		}

		while (0 < pendingPairCards.length) {
			const card = pendingPairCards.pop();
			const pairCard = getPairCard(card);

			if (!pending.has(card) || !pending.has(pairCard)) {
				continue;
			}

			pending.delete(card);
			pending.delete(pairCard);
			coin -= 2;
			availablePairCount += 1;
			return true;
		}

		return false;
	};

	for (let i = 0; i < initialHandSize; i += 1) {
		const card = cards[i];
		const pairCard = getPairCard(card);

		if (hand.has(pairCard)) {
			hand.delete(pairCard);
			availablePairCount += 1;
			continue;
		}

		hand.add(card);
	}

	let round = 0;

	while (round < maxRounds) {
		const drawStart = initialHandSize + round * 2;
		const drawnCards = [cards[drawStart], cards[drawStart + 1]];

		for (const card of drawnCards) {
			const pairCard = getPairCard(card);

			if (1 <= coin && hand.has(pairCard)) {
				hand.delete(pairCard);
				coin -= 1;
				availablePairCount += 1;
				continue;
			}

			addPendingCard(card);
		}

		const hasPlayablePair = round < availablePairCount;

		if (!hasPlayablePair && !usePendingPair()) {
			break;
		}

		round += 1;
	}

	return round + 1;
};

[프로그래머스] 258707 n + 1 카드 게임 (javascript)

문제

풀이

정답 코드

Share this post