1010. Pairs of Songs With Total Durations Divisible by 60

Leetcode 1010번 풀이

문제

Pairs of Songs With Total Durations Divisible by 60

풀이 1

아이디어

두 곡의 재생 시간 합이 60의 배수인 쌍을 구해야 한다. 브루트 포스로 모든 쌍을 확인하면 O(N²)이지만, time의 크기가 최대 6×10⁴이므로 시간 초과가 발생한다.

그래서 1000 이하의 60의 배수(60, 120, …, 960) 집합을 미리 준비하고, 각 곡 t를 순회하면서 total - t가 이전에 등장한 적 있는지 Map에서 조회하는 방법을 썼다.

순서를 고려하지 않는 단순 쌍이기 때문에 이대로만 하면 순서가 뒤바뀐 쌍이 중복으로 세어진다. 따라서 Map을 미리 채우지 않고, 짝을 먼저 찾은 뒤 현재 t를 Map에 등록하는 순서로 처리한다. 이렇게 하면 인덱스 i < j인 방향으로만 쌍이 카운트되어 중복이 발생하지 않는다..

코드

function numPairsDivisibleBy60(time: number[]): number {
  const totals = new Set([60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, 720, 780, 840, 900, 960]);
  const timeMap = new Map(); // key: time, value: count. 이 map 안에서만 찾을 것임. (중복 방지)

  let answer = 0;
  for (const t of time) {
    for (const total of totals) {
      if (total < t) continue;
      answer += timeMap.get(total - t) ?? 0;
    }
    timeMap.set(t, (timeMap.get(t) ?? 0) + 1);
  }

  return answer;
}

시간 / 공간 복잡도

• 시간 복잡도: O(N) — 60의 배수 집합 크기가 상수(16개)이므로 각 원소당 O(1) 처리
• 공간 복잡도: O(N) — 최악의 경우 모든 시간 값을 맵에 저장

풀이 2

아이디어

풀이 1과 동일한 구조이지만, 실제 시간 값 대신 60으로 나눈 나머지를 Map의 키로 사용한다.

(a + b) % 60 == 0이 되려면 두 나머지의 합이 0 또는 60이어야 한다. 따라서 현재 t의 나머지가 rem일 때, 짝이 되는 나머지(complement)는 다음과 같다.

• rem == 0이면 → complement = 0
• 그 외엔 → complement = 60 - rem

이렇게 하면 내부 루프 없이 O(1)로 짝을 조회할 수 있고, Map의 키 범위도 0~59로 고정된다.

코드

function numPairsDivisibleBy60(time: number[]): number {
  const remainderMap = new Map<number, number>(); // key: t % 60, value: count

  let answer = 0;
  for (const t of time) {
    const rem = t % 60;
    const complement = rem === 0 ? 0 : 60 - rem;
    answer += remainderMap.get(complement) ?? 0;
    remainderMap.set(rem, (remainderMap.get(rem) ?? 0) + 1);
  }

  return answer;
}

시간 / 공간 복잡도

• 시간 복잡도: O(N) — 각 원소를 한 번씩 순회
• 공간 복잡도: O(1) — Map의 키가 0~59로 고정 크기

여담

hash를 사용해야겠다는 사실은 잘 떠오르는데, 어떻게 써야 하는지 한번에 떠오르질 않아서 풀이 시간이 너무 오래 걸린다 ㅠㅠ