[1스4코2파] # 250. LeetCode 846. Hand of Straights

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (250일차)
[4코1파] 2023.01.13~ (243일차)
[1스4코1파] 2023.04.12~ (154일차)
[1스4코2파] 2023.05.03 ~ (132일차)

Today :

2023.09.10 [250일차]
846. Hand of Straights
https://leetcode.com/problems/hand-of-straights/

846. Hand of Straights

문제 설명

Alice가 가진 카드를 원소로 가지는 카드 배열 hand가 주어지는데,
hand[i]가 i번째 카드에 기록된 값이고 정수 groupSize인 정수 배열 손이 주어지면 카드를 재배열할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환

문제 풀이 방법

hashMap으로 카드 원소에 대한 count dictionary를 구성하고,
mInHeap을 사용해서, hashMap에 있는 가장 작은 원소부터 그룹사이즈에 해당하는
연속적인 원소의 서브 원소들을 탐색한 후에 return 한다.
hashmap과 MinHeap으로 O(n*log(n))으로 찾을 수 있음

내 코드

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False

        cnt = {}
        for n in hand:
            cnt[n] = 1+ cnt.get(n,0)

        minHeap = list(cnt.keys())
        heapq.heapify(minHeap)

        while minHeap:
            first = minHeap[0]

            for i in range(first, first+ groupSize):
                if i not in cnt:
                    return False
                cnt[i] -= 1

                if cnt[i] == 0:
                    if i != minHeap[0]:
                        return False
                    heapq.heappop(minHeap)
        
        return True

증빙

여담

어렵네 ;;