프로그래머스 - 요격 시스템

문제

프로그래머스 — 요격 시스템

접근 방법

각 미사일을 개구간 (start, end)로 보고, 모든 구간을 관통하는 요격 위치의 최소 개수를 구한다. 종료 지점을 기준으로 선택하는 그리디 풀이이며, 서로 겹치지 않는 회의를 고르는 회의실 배정과는 선택 대상이 다르다.

구간을 종료 지점의 오름차순으로 정렬한다. 아직 요격하지 않은 구간 중 가장 빨리 끝나는 구간의 end 바로 왼쪽에 요격 위치를 잡는다. 이 구간을 반드시 관통해야 하며, 가능한 한 오른쪽에 잡으면 종료 지점이 더 늦은 구간도 함께 관통할 수 있다.

좌표가 정수이므로 end - 0.5를 선택하면 이 조건을 만족한다. 이후 구간의 종료 지점은 선택한 end 이상이므로, 해당 구간의 시작 지점이 end보다 작으면 같은 요격으로 처리할 수 있다.

코드에서는 실제 좌표 대신 선택 기준이 된 end를 shotBoundary에 저장한다. 다음 구간의 start >= shotBoundary이면 새 요격이 필요하며, 그 구간의 종료 지점으로 기준을 갱신한다. start === shotBoundary일 때도 새 요격이 필요한 이유는 구간의 끝점이 포함되지 않기 때문이다.

코드

function solution(targets) {
  const sortedTargets = targets.slice().sort((a, b) => a[1] - b[1])
  let answer = 0
  let shotBoundary = -Infinity

  for (const [start, end] of sortedTargets) {
    if (start >= shotBoundary) {
      answer += 1
      shotBoundary = end
    }
  }

  return answer
}

복잡도와 경계 조건

구간 수가 n이면 시간은 정렬을 포함해 O(n log n)이다. 입력 배열을 복사하므로 추가 공간은 O(n)이다.

(1, 2)와 (2, 3)은 끝점만 맞닿아 있어 두 번 요격해야 한다. 같은 구간이 반복되거나 여러 구간이 하나의 위치를 공유하면 한 번으로 처리할 수 있다.