leetcode.com 846. Hand of Straights

 

문제 링크: https://leetcode.com/problems/hand-of-straights/description/

파이썬 소스: https://bit.ly/3wNfRes

Hand의 길이와 groupSize에 따라서, 이문제는 그룹을 나눌수 없는 경우가 있습니다.

바로 아래와 같은 경우처럼, 나머지가 0이 아닌 경우입니다.

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

 

1개의 그룹에 들어가는 숫자의 개수는 groupSize이고, 각 그룹에 들어가는 숫자는 연속되어야 하며, 그룹에 들어가는 숫자들은 hand 리스트에서 꺼내서 사용합니다.

첫번째로 생각할 부분은 hand 안에 중복된 숫자들이 들어있다.

두번째로 생각할 부분은 hand 안에 들어 있는 숫자들은 정렬이 되어 있지 않다.

Example 1번에 보면 첫번째 그룹이 1,2,3, 두번째 그룹이 2, 3, 4 인대요, 첫번째 그룹과 두번째 그룹의 숫자들을 정렬해 보면, 1, 2, 2, 3, 3, 4 가 됩니다.

2가 2번, 3이 2번 중복되어서, 첫번째 그룹 1, 2, 3 을 선택하기가 어렵습니다.

Counter()를 사용해서 hand 리스트에 들어 있는 숫자와, 각 숫자가 몇 번 hand에 들어있는지 딕셔너리 형태로 변환할 수 있습니다.

 

문제를 풀기 시작하려면, 가장 작은 숫자를 찾아야 합니다. 딕셔너리형태로 바뀌었으니 keys() 메서드를 키를 받아 와서, 정렬하면, 제일 앞에 key가 가장 작은 숫자일 것입니다.

하지만, 딕셔너리의 key의 순서는 항상 정렬되어 있다고 보장할 수 없기 때문에, 첫번째 인 1을 사용한 뒤에 딕셔너리에서 삭제하고, keys()를 다시 정렬해야 되서, 속도가 느려질 수 있습니다.

이 부분은 heapq를 사용해서 해결 할 수 있습니다. 튜플의 형태로(숫자, 숫자의 횟수)를 heappush()를 하면, heappop()을 했을 때 항상 가장 작은 숫자가 리턴됩니다.

class Solution:     def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:         if 0 != len(hand) % groupSize:             return False         hands = Counter(hand)         heap, removes = [], []         for item in hands.items():             heapq.heappush(heap, item)

 

이제 heap 에 원소가 있는 동안 while 루프를 돌면서 하나씩 꺼내 서 그룹을 만들어 보겠습니다.

heappush() 메서드로 item을 넣었기 때문에 heap 에는 오름차순으로 숫자가 정렬되어 있습니다.

그룹의 첫번재 숫자를 알기 위해서, heappop()을 합니다. 꺼네온 숫자 t의 길이(length)는 1감소 시켜주고, removes 에 append() 해줍니다.

 그 다음으로는, 다시 heappop()을 해서, 두개의 숫자가 연속되는지, 즉 값이 1이 증가 했는지 확인해 보아야 합니다. 첫번째 숫자는 t, 두번째 숫자는 t1 이러고 코드를 작성했습니다.

이 때, heap이 비어 있을 수도 있기 때문에, heap 이 비어 있는지 꼭 확인해야 합니다.

 t + 1 == t1 이라면, t 값을 t1값으로 변경하고, t1의 길이를 1감소시킨뒤 removes 리스트에 append() 해줍니다.

t + 1 == t1 성립하지 않으면, 연속된 숫자가 없는 것이므로 그룹을 나눌 수 없기에 return False 입니다.

while heap:     t, length = heapq.heappop(heap)     removes.append((t, length-1))     for i in range(1, groupSize):         if len(heap) <= 0:             return False         t1, length = heapq.heappop(heap)         if t + 1 == t1:             t = t1             removes.append((t1, length - 1))         else:             return False

 

이번 그룹을 만드는대 사용된 숫자는 removes 리스트에 들어 있습니다. Length가 0보다 큰 숫자는 다시 사용해야 함으로 다시 heappush()를 해줍니다.

for item in removes:     if item[1] > 0:         heapq.heappush(heap, item) removes.clear()

 

이렇게 마지막까지 while heap 루프를 실행하게 되면, 각 숫자를 문제가 원하는 조건으로 그룹을 만들었으므로, return True입니다.

from collections import Counter from typing import List import heapq class Solution:     def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:         if 0 != len(hand) % groupSize:             return False         hands = Counter(hand)         heap, removes = [], []         for item in hands.items():             heapq.heappush(heap, item)         while heap:             t, length = heapq.heappop(heap)             removes.append((t, length-1))             for i in range(1, groupSize):                 if len(heap) <= 0:                     return False                 t1, length = heapq.heappop(heap)                 if t + 1 == t1:                     t = t1                     removes.append((t1, length - 1))                 else:                     return False             for item in removes:                 if item[1] > 0:                     heapq.heappush(heap, item)             removes.clear()         return True

코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul