[LeetCode] 822. Card Flipping Game

문제 요약

• 카드마다 앞면 fronts[i], 뒷면 backs[i]에 숫자가 적혀 있다.
• 카드는 원하는 만큼 뒤집을 수 있다.
• 뒤집은 뒤 카드 하나를 골라 뒷면 숫자가 어떤 카드의 앞면에도 없으면 그 숫자는 "좋은 숫자"다.
• 좋은 숫자의 최솟값을 구한다. 없으면 0을 반환한다.

핵심 아이디어

"지금 앞면에 없는 숫자"를 찾는 문제가 아니다. 뒤집어서 앞면에서 전부 치울 수 있는 숫자를 찾는 문제다.

• [x, 5] 카드: 뒤집어서 x를 뒤로 보내면 된다. 치울 수 있다.
• [x, x] 카드: 어떻게 뒤집어도 x가 앞면에 남는다. 치울 수 없다.

👉 앞뒤가 같은 카드의 숫자만 후보에서 빠지고, 나머지는 전부 후보다.

풀이

1. 앞뒤가 같은 카드의 숫자를 cantFlip에 모은다.
2. 앞면과 뒷면의 모든 숫자 중 cantFlip에 없는 숫자의 최솟값을 구한다.
3. 후보가 없으면 0을 반환한다.

function flipgame(fronts: number[], backs: number[]): number {
    const cantFlip = new Set<number>();
    for (let i = 0; i < fronts.length; i++) {
        if (fronts[i] === backs[i]) cantFlip.add(fronts[i]);
    }

    let min = Infinity;
    for (const num of [...fronts, ...backs]) {
        if (!cantFlip.has(num)) min = Math.min(min, num);
    }

    return min === Infinity ? 0 : min;
};

복잡도

• 시간: O(n)
• 공간: O(n)

처음에 틀린 이유

• 카드를 한 번 순회하면서 바로 판정했다. 그러면 뒤에 나오는 [x, x] 카드가 앞에서 이미 고른 x를 무효로 만들지 못한다. 금지 목록을 먼저 다 만든 뒤에 판정해야 한다.
• 금지 조건을 앞뒤 중 큰 값으로 잘못 잡았다. 진짜 금지 조건은 앞뒤가 같은 카드다.
• 답이 없을 때 Infinity를 그대로 반환했다. 문제는 0을 요구한다.