What is the best way to solve Hand of Straights?

The optimized O(n) approach using Greedy patterns is generally preferred.

상위 150개 인터뷰쉬움

스트레이트의 손

'Hand of Straights' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

Alice는 몇 장의 카드를 가지고 있으며 각 그룹의 크기가 groupSize이고 연속된 groupSize 카드로 구성되도록 카드를 그룹으로 재배열하려고 합니다. hand[i]가 i번째 카드에 기록된 값이고 정수 groupSize인 정수 배열 손이 주어지면 카드를 재배열할 수 있으면 True를 반환하고 그렇지 않으면 False를 반환합니다.

isNStraightHand(hand: List[int], groupSize: int) -> bool 함수를 작성하세요.

제약

•1 <= len(hand) <= 10^4
•0 <= hand[i] <= 10^9
•1 <= groupSize <= len(hand)

예

Example 1

Input

hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

Output

True

Explanation

[1,2,3], [2,3,4], [6,7,8] are consecutive groups of 3.

Example 2

Input

hand = [1,2,3,4,5], groupSize = 4

Output

False

Explanation

Cannot rearrange cards into consecutive groups of 4.

Need a Hint?

세트나 힙과 같은 Greedy 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

Greedy 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

import heapq, collections
def is_n_straight_hand_opt(hand, groupSize):
    if len(hand) % groupSize: return False
    count = collections.Counter(hand)
    minH = list(count.keys()); heapq.heapify(minH)
    while minH:
        first = minH[0]
        for i in range(first, first + groupSize):
            if i not in count: return False
            count[i] -= 1
            if count[i] == 0:
                if i != minH[0]: return False
                heapq.heappop(minH)
    return True

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def is_n_straight_hand_brute(hand, groupSize):
    if len(hand) % groupSize: return False
    hand.sort()
    while hand:
        first = hand.pop(0)
        for i in range(1, groupSize):
            if (first + i) not in hand: return False
            hand.remove(first + i)
    return True