.leetcode(846. Hand of Straights)

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

 

1. 2022.02.05 시도

소요시간: 35분(11분 구상, 24분 코딩)

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {        
        if ((hand.length % groupSize) != 0) {
            return false;
        }

        // sort
        Arrays.sort(hand);
        List<Integer> nums = new ArrayList<>();
        List<Integer> counts = new ArrayList<>();
        int prev = -1;
        for (int i=0; i< hand.length; i++) {
            if (prev == hand[i]) {
                counts.set(counts.size()-1, counts.get(counts.size()-1) + 1);
            } else {
                nums.add(hand[i]);
                counts.add(1);
                prev = hand[i];
            }
        }
        
        int i = 0;
        int n = 0;
        while ( i < (hand.length / groupSize)) {
            if (n >= hand.length) {
                return false;
            }

            int startNum = nums.get(n);
            for (int x=0; x<groupSize; x++) {
                if (counts.size() <= n+x) {
                    return false;
                }
                if (counts.get(n+x) == 0) {
                    return false;
                }
                if (startNum+x != nums.get(n+x)) {
                    return false;
                }
                counts.set(n+x, counts.get(n+x) - 1);
            }
            
            int old = n;
            n = n + groupSize;
            for (int x=0; x<groupSize; x++) {
                if (counts.get(old+x) > 0) {
                    n = Math.min(n, old+x);
                }
            }
            i++;
        }
        
        return true;
    }
}

풀이 접근 과정

groupSize 배수여야지 나눌 수 있기때문에 우선 예외처리를 포함시켜야겠다.

정렬은 필요하겠다.

정렬에서 숫자를 수집할 때, map으로 해도 되고 혹은 list두개를 써야겠다. LinkedHashMap을 사용하면 FIFO로 저장되어서 쓸 수 있는데 나는 list 두개로 써보기로 했다.

하나의 그룹이 선택되고 다음 그룹이 어떤 숫자로 될지를 알 수 있을까 고민했다. 첫번째 선택이 끝나야지만 알 수 있겠다 싶었다. 그래서 while문을 크게 돌리고 내부에서 for문을 돌려서 카운트 된 숫자를 -1하는 식으로 찾아가기로 했다.

시간복잡도는 정렬에 nlogN이 걸리고 while문은 사실상 중첩for문이 있지만 딱 n걔만 돌개되어 있다. 따라서 nlogN정도로 예상했다.

느낀점

• 이 문제의 핵심은 consecutive이다. 즉 연속적인 숫자라는 문제의 전제가 중요하다.
• TreeMap을 쓰면 따로 정렬을 하지않아도 key값에 따라 정렬해준다. 그러면 정렬+LinkedHashMap  or 정렬+ArrayList2개  or  TreeMap을 쓸 수 있다고 볼 수 있다.
  • Return Type: A set having the keys of the treemap in ascending order.
• 위에 나는 여러 케이스를 굉장히 구구절절 썼다.. 그런데 다른 사람들 discussion보니 쉽게 푼게 있어서 가져왔다. 설명에 써있는데 treeMap에 모든 데이터를 넣는데 O(nlogN)이 들고 for문은 O(n)이 들기에 시간복잡도는 이것도 O(nlogN)이라 볼 수 있다. 그리고 공간에 대해서도 적혀있다. 공간도 모든 요소다 다 다르다면 N개 필요하므로 O(n)이라 할 수 있다.
  • 여기서 treeMap.put(num+i, c-count)에서 count갯수만큼 빼주는건 keySet에 대해 한번만 확인하기 때문이다. [1,1,2,2,3,3] 이고 groupSize가 3인 경우, 한번에 2개씩 빼줘야 제대로 검증이 되기때문이다.

// https://leetcode.com/problems/hand-of-straights/discuss/135700/Short-Java-solution!
class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {        
        Map<Integer, Integer> treeMap = new TreeMap<>();
        
        for (int each: hand) {
            treeMap.put(each, treeMap.getOrDefault(each, 0)+1);
        }
     
        for (int num: treeMap.keySet()) {
            int count = treeMap.get(num);
            if (count == 0) {
                continue;
            }
            
            for (int i=0; i<groupSize; i++) {
                Integer c = treeMap.get(num+i);
                if (c == null || c == 0) {
                    return false;
                }
                
                treeMap.put(num+i, c-count);
            }
        }
        
        return true;
    }
}

• PriorityQueue로도 풀 수 있는 방법이 있어서 가져왔다. PriorityQueue는 낮은 숫자를 최우선을 주고 있기때문에 그 성질을 이용한 것이고 또한 특정 요소를 remove라는 메소드를 사용해서 제거하면서 원하는 결과를 얻을 수 있다.

// https://leetcode.com/problems/hand-of-straights/discuss/136200/Simple-Java-solution-using-priority-queue
class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {        
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int each: hand) {
            priorityQueue.add(each);
        }
        
        while(priorityQueue.size() != 0) {   
            int nums = priorityQueue.poll();
            for(int i=nums+1; i<nums+groupSize; i++) {
                if (priorityQueue.remove(i)) {
                    continue;
                }
                
                return false;
            }
        }
        
        return true;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형