[LeetCode] 846. Hand of Straights

https://leetcode.com/problems/hand-of-straights/description/

leetcode - Hand of Straights

문제 유형 : 우선순위 큐, 그리디, 해시

문제 난이도 : Medium

 

문제

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

 

앨리스는 손에 카드들을 들고 있다.

groupSize개씩 분류하고 싶고, 인접한 수들끼리 구성되도록 하고싶다.

할 수 있는지에 대한 여부를 반환하시오.

 

풀이

해시맵에 각 카드 숫자의 개수를 저장시킨다.

우선순위 큐에 숫자별로 하나씩만 넣는다.

 

우선순위 큐에 요소가 있는 동안, 다음을 반복한다:

1. 하나 pop한다. 첫번째 수가 될것이고, 그룹에 카드가 하나 있다. 해시맵에 개수도 하나 줄인다.

2. groupSize-1번만큼 다음을 수행한다:

    만약 우선순위큐의 톱이 이전 pop한 숫자보다 1 크다면, 1번을 반복한다. 아니라면 false를 반환한다.

3. 그룹의 각 요소별로, 해시맵에 카운트가 양수임을 확인하면, 다시 우선순위 큐에 넣는다.

 

우선순위 큐를 비워내면, true를 반환한다.

 

코드

C++

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if(hand.size() % groupSize) {
            return false;
        }
        
        unordered_map<int, int> freq;
        for(const auto &card : hand) {
            freq[card]++;
        }

        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto element : freq) {
            pq.push(element.first);
        }

        while(!pq.empty()) {
            int curr = pq.top();
            pq.pop();
            freq[curr]--;
            

            for(int i = 1; i < groupSize; i++) {
                if(pq.top() != curr+1) return false;

                curr++;
                pq.pop();
                freq[curr]--;
            }

            for(int i = 0; i < groupSize; i++) {
                if(freq[curr - i] > 0) pq.push(curr - i);
            }
        }

        return true;
    }
};