🎈 문제 풀이

가장 먼저 문제에서 말하는 풀하우스가 무엇인지를 살펴봅시다. 패에서 풀하우스를 만들기 위해서는 같은 숫자가 적힌 3장의 카드와 또 다른 같은 숫자가 적힌 2장의 카드가 필요합니다. 이를 통해 우리는 아래 두 가지 사실을 알 수 있습니다.

1. 풀하우스 조건의 달성 여부는 각 숫자가 패에 몇 개 존재하는지에 의해 결정된다.
2. 개수가 중요할 뿐, 카드에 적힌 숫자가 무엇이었는지는 중요하지 않다.

위와 같은 힌트를 곱씹어보면, 패를 [1,2,2,1,1]와 같이 리스트로 나타내는 것이 아니라

{1이 3장,2가 2장}과 같은 개수로 표현하는 것이 패의 상태를 더 잘 나타내는 방법임을 알 수 있습니다.

[1, 2, 2, 1, 1], [3, 2, 3, 3, 2], [1, 4, 4, 4, 1] 등 풀하우스를 만드는 카드의 조합은 셀 수 없이 많겠지만,

이들을 { x이 3장, y가 2장 } 으로 표현하면

가장 많은 것이 3장, 두 번째로 많은 것이 2장 있으므로

풀하우스를 만들 수 있다는 사실을 쉽게 확인할 수 있기 때문입니다.

이러한 표현 방식을 이용하면 패에 카드를 한 장 씩 추가하면서

현재 패가 풀하우스를 이루는지 판별하는 것이 간단해집니다.

조커가 없는 간단한 상황이라면 패에서 가장 많은 개수 $m_1$과 두 번째로 가장 많은 개수 $m_2$가 각각 3 이상, 2 이상이라면 해당 패로 풀 하우스를 만들 수 있다는 것이 보장될 것입니다.
(즉, $m_1 ≥ 3$ 이고 $m_2 ≥ 2$ 이면 풀하우스 구성 가능)

그렇다면 조커가 있는 상황이라면 어떨까요?

조커는 어떤 숫자로든 이용될 수 있다는 사실이 조금 어렵게 다가올 수 있지만,

사실상 조커를 $m_1$이나 $m_2$를 보충하는데 이용하는 것이 최선임을 직관적으로 알 수 있습니다.

그래서 조커의 수를 $k$라고 하였을 때,

"$m_1$과 $m_2$에서 부족한 수량"이 $k$이하면 조커를 이용해 풀하우스의 조건을 충족시킬 수 있게 됩니다

(즉, $max(3 - m_1, 0) + max(2 - m_2, 0) ≥ k$라면 풀하우스 구성 가능)

여기까지의 전개로 현재 패가 풀하우스를 구성할 수 있는지 판별하는 방법을 알 수 있었습니다.

그런데 문제를 다시 보면 풀하우스를 구성하게 되면 무조건 패의 모든 카드를 버린다고 되어있습니다.
그렇다면 풀하우스는 언제 구성하는 것이 전체 풀하우스 횟수를 최대화할까요?

풀하우스를 만들면 풀하우스 5장에 포함되지 않는 다른 카드들도 모두 버리게 되지만,
풀하우스를 최대한 많이 만들기 위해서는

카드를 아끼지 않고 만들 수 있을 때마다 무조건 만드는 것이 이득입니다.

조커와 같이 유용하게 쓰일 수 있는 카드를 아끼는 전략은

실질적으로 무의미하게 소모되는 카드의 수를 증가시키고,
풀하우스를 항상 만드는 전략과 같은 풀하우스 횟수를 달성한 시점에서 패에 카드를 적게 가지게 됩니다.

위에서 설명한 전략을 그대로 코드로 구현하면 문제를 해결할 수 있습니다.

{ key1: value1, key2: value2, ... } 와 같이 키(Key)와 그에 대응하는 값(Value)의 쌍들의 집합을 표현하는 것에는 맵(Map)이나 사전(Dictionary) 자료구조를 이용하는 것이 일반적입니다.

하지만 이 문제에서는 키에 해당하는 카드에 적힌 숫자가 0이상 13이하의 좁은 자연수 범위이므로

맵 자료구조를 사용하지 않고 간단한 배열을 사용하는 것 만으로도 각 숫자의 개수를 셀 수 있습니다.

이렇게 패에 존재하는 숫자들의 개수를 세 주었다면

그 다음으로 가장 많은 개수 $m_1$과 두 번째로 많은 개수 $m_2$를 구해주는 것은
개수를 내림차순으로 정렬하고 앞의 두 원소 를 선택하는 것으로 구현할 수 있습니다.

import java.util.Arrays;
import java.util.Collections;

public class Solution {
    public int solution(int[] cards) {
        int collected = 0;
        // 각 숫자의 등장 횟수를 저장하기 위한 정수 배열.
        // 배열이 아닌 TreeMap 등을 이용해도 무방.
        Integer[] count = new Integer[14];
        Arrays.fill(count, 0);

        for (int i = 0; i < cards.length; ++i) {
            count[cards[i]]++;

            // 현재 패에 있는 카드의 개수들을 큰 것부터 정렬하여 첫번째 값과 두번째 값을 봄.
            Integer[] sub = Arrays.copyOfRange(count, 1, 14);
            Arrays.sort(sub, Collections.reverseOrder());

            // 조커를 통해 부족한 분량을 보충할 수 있다면 정답을 증가시키고 패를 모두 버림.
            int need = Math.max(3-sub[0], 0) + Math.max(2-sub[1], 0);
            if (need <= count[0]) {
                collected++;
                Arrays.fill(count, 0);
            }
        }
        return collected;
    }
}