✶ [Two Pointer,HashMap 문제] Leetcode 846. Hand of Straights

문제

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

상기 문제를 요약해보면 주어진 hand 에서 제시된 그룹사이즈만큼으로 배열을 나누어야 한다. 그 배열 내 숫자는 연속적으로 인접한 수가 나오도록 배분할 수 있는지에 관한 문제이다. (배열 간 숫자의 연속성은 불필요)

문제풀이

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        n = len(hand)
        
        # 그룹 크기가 1인 경우 항상 True를 반환합니다.
        if groupSize == 1:
            return True
        
        # 그룹 크기로 나누어 떨어지지 않으면 False를 반환합니다.
        if n % groupSize != 0:
            return False
        
        # 포인터 및 변수 초기화
        l, r = 0, 0
        visited = [True] + [False] * (n - 1)
        cnt, cnt_batch = 1, 0
        hand.sort()
        prevVal = hand[l]
        
        # 그룹 형성 여부 검사
        while r < n:
            # 이미 방문한 원소이거나 이전과 같은 값인 경우, 다음 원소로 이동
            if visited[r] or hand[r] == prevVal:
                r += 1
                continue
            
            # 현재 원소가 이전 원소보다 1 크면서, 그룹이 연속된 경우가 아니라면 False 반환
            if hand[r] > prevVal + 1 and r != l:
                return False
            
            # 현재 원소를 그룹에 포함시키고 포인터 및 변수 업데이트
            visited[l], visited[r], prevVal = True, True, hand[r]
            r += 1
            cnt += 1
            
            # 그룹이 완성되면 그룹 개수를 증가시키고, 모든 그룹이 완성되면 True 반환
            if cnt == groupSize:
                cnt_batch += 1
                if cnt_batch * cnt == n:
                    return True
                
                # 다음 그룹을 찾기 위해 포인터 이동
                while visited[l]:
                    l += 1
                visited[l] = True
                r = l
                cnt, prevVal = 1, hand[l]
        
        # 그룹 개수가 groupSize와 일치하지 않으면 False 반환
        return True if cnt == groupSize else False

        

핵심 코드 설명

위 코드는 주어진 hand를 오름차순으로 정렬 후 투포인터 방식으로 탐색해나가고 있다.
핵심은 While 문 내에 존재하며 배열 중 방문하지 않은 원소 내에 가장 작은 값을 l 변수로 고정한 후 r변수를 하나씩 증가해나가면서 연속성이 존재하는지를 탐색해 나간다. 상세 세부 동작은 코드 주석 및 아래 예시를 참고하도록 하자.

동작방식(예시)

Lookback

1. 이번 문제는 연관된 문제 분류로 볼때 Two Pointer는 아니고 HashMap 으로 분류되는 문제였다. 이번 문제에 대해서 나는 Two Pointer로 접근하였는데 속도,메모리 면에서 99%% 수준의 최적화된 솔루션을 만들 수 있었는데 이는 여러 문제를 풀면서 얻어온 스킬(Two Pointer, 좌우 탐색 등)이 누적이 되었기 때문이지 않을까 싶다. 아직은 코딩에 미숙한 수준이지만 그래도 하나씩 나아가고 있다는 것을 스스로 느낄때 큰 원동력이 되는 듯하다.(뿌듯)