594. Longest Harmonious Subsequence

리트코드 594번 풀이

문제

Longest Harmonious Subsequence

풀이 1

아이디어

처음에는 투포인터처럼 포인터 두개를 이동시켜가면서 최대 길이를 구하려고 했었다. 그런데 구현하면서 보니 흐름이 직관적이지 않아서 Map을 활용하는 다른 방법으로 풀이했다.

1. Map을 이용해 각 숫자와 등장 횟수를 저장한다.
2. Map의 key를 정렬한다.
3. 정렬된 key를 순회하면서 key의 차이가 1인 경우 등장 횟수의 합을 구해서 최대값을 갱신한다.
4. 최대값을 반환한다.

key를 정렬했던 이유는 key의 차이가 1인 경우를 쉽게 찾기 위해서였다. 정렬된 key를 순회하면서 바로 이전 key와의 차이를 비교하면 되기 때문이다.

코드

function findLHS(nums: number[]): number {
  const map = new Map();
  for (const num of nums) {
    map.set(num, (map.get(num) ?? 0) + 1);
  }

  const keys = [...map.keys()].sort((a, b) => a - b);
  let max = 0;
  for (let idx = 1; idx < keys.length; idx++) {
    if (keys[idx] - keys[idx - 1] === 1) max = Math.max(max, map.get(keys[idx - 1]) + map.get(keys[idx]));
  }

  return max;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n log n) — Map 구성 O(n) + key 정렬 O(k log k), k ≤ n
• 공간 복잡도: O(n) — Map과 keys 배열

풀이 2

아이디어

풀이 1을 풀면서 가장 찜찜했던 부분이 바로 Key를 정렬하는 부분이었다. 정렬할 원소를 줄이겠다고 전체 원소 대신 Key를 정렬하는 식으로 하긴 했지만 그래도 좀 무의미할수도 있겠다는 생각이 들었다. 역시나, 정렬을 하지 않고도 풀 수 있는 방법이 있었다.

풀이 1과 동일한 접근이지만, 이번에는 Map의 key를 정렬하지 않고, Map의 key를 순회하면서 바로 다음 key가 존재하는지 확인하는 방식으로 풀이했다. 이렇게 하면 key를 정렬할 필요가 없어서 시간 복잡도가 O(n)으로 줄어든다.

코드

function findLHS(nums: number[]): number {
  const map = new Map();
  for (const num of nums) {
    map.set(num, (map.get(num) ?? 0) + 1);
  }

  let max = 0;
  for (const key of map.keys()) {
    if (map.has(key + 1)) max = Math.max(max, map.get(key) + map.get(key + 1));
  }

  return max;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n) — Map 구성 O(n) + Map 순회 O(n)
• 공간 복잡도: O(n) — Map 저장