프로그래머스 < 요격 시스템 > JavaScript

📍문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/181188

 

📍알고리즘 분류

- 그리디

 

📍문제 풀이

[시작 좌표, 종료 좌표] 가 배열로 주어진다

const targets = [
  [4, 5],
  [4, 8],
  [10, 14],
  [11, 13],
  [5, 12],
  [3, 7],
  [1, 4],
];

 

이 좌표들을 선으로 그었을 때, 모든 수평선을 수직으로 가로지르는데 필요한 최소한의 수직선의 갯수를 구하면 된다.

그림으로 나타내면, 아래처럼 표현할 수 있는데, 겹치지 않는 수평선이 총 3개 이므로, 최소 3개의 수직선이 필요하다.

 

겹치지 않는 수평선인지 아닌지를 빠르게 파악하려면, 모든 좌표들을 종료지점을 기준으로 오름차순 정렬한 후, 순서대로 검사해나가면 된다.

 

좌표들의 배열이 정렬된 상태이므로, 가장 최적의 해를 구할 수 있다는 점에서 그리디 문제라고 할 수 있다.

 

📍코드 (JavaScript)

function solution(targets) {
  const sortedTargets = targets.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    return a[1] - b[1];
  });
  let result = 0;
  let latestEnd = -1; // 1번째 loop에서 무조건 초기화하기 위해
  for (const [start, end] of sortedTargets) {
    // 새로운 수평선 등장
    if (start >= latestEnd) {
      latestEnd = end;
      result++;
    }
  }
  return result;
}