846. Hand of Straights

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

hand에 존재하는 카드 배열이 주어진다. groupSize의 크기만큼 숫자가 이어지도록 모든 카드를 그룹지을 수 있는 경우 true 아니면 false를 반환하는 문제다.

Solution

Map & greedy

카드들이 주어졌을 때, 순서대로 묶어서 그룹지을 때 항상 가장 작거나 가장 큰 숫자부터 접근해서 Greedy하게 제거하는 것이 정답이다. 중간에서 제거할 경우 나중에 양쪽이 남게 되는 경우의 수가 있기 때문이다. 따라서 카드 그룹을 숫자 순서대로 정렬해야 하는데 단순히 sort를 하면 중복된 카드들을 연산하기 힘들기 때문에 각 카드들의 개수를 먼저 map으로 만들어 저장한다. 카드 => 카드 개수로 저장되있는 map 자료구조의 key들을 정렬해 greedy 하게 앞에서부터 그룹화 시켜서 제거를 시도한다. 모든 카드들이 그룹지어져서 제거된다면 true를 반환하고 중간에 카드가 부족하거나 남는 경우는 false를 반환한다.

Algorithm

• 가장 단순한 예외처리로 hand크기가 groupSize의 배수가 아닐 경우 false를 반환한다.
• hand의 카드들의 card => count로 맵핑하는 myMap을 만든다.
• myMap에 존재하는 key들을 sort한다.
• 가장 작은 카드부터 그룹지어서 myMap으로부터 제거한다.
• 제거 중에 카드가 없거나 부족한경우(음수) false를 반환한다.
• 마지막까지 모든 카드를 그룹지어 제거했다면 true를 반환한다.

var isNStraightHand = function(hand, groupSize) {
  // sort & greedy
  // map & greedy
  
  // Easy breakout point
  if (hand.length % groupSize !== 0) return false;

  // Map (card => count)
  const myMap = new Map();
  for (let card of hand) {
    myMap.set(card, (myMap.get(card) ?? 0) + 1);
  }

  // Sort & greedy
  const sortedKey = Array.from(myMap.keys()).sort((a, b) => a - b);
  for (let key of sortedKey) {
    if (myMap.get(key) < 0) return false;
    const cardLeft = myMap.get(key);
    if (cardLeft === 0) continue;
    for (let i = 0; i < groupSize; i++) {
      const calIdx = key + i;
      if (!myMap.has(calIdx)) return false;
      myMap.set(calIdx, myMap.get(calIdx) - cardLeft);
    }
  }

  return true;
};

여러 처리 과정을 거치지만 myMap에서 O(n)의 공간 복잡도, 그리고 정렬 알고리즘의 O(nlogn)의 시간 복잡도가 가장 큰 영향을 끼친다.