[알고리즘 연습] 프로그래머스 요격 시스템 (LEVEL 2, 자바스크립트)

문제

프로그래머스

---

풀이

현재 폭격 미사일이 이전 폭격 미사일의 범위 안에 있을 때, 이전 폭격 미사일의 범위와 겹칠 때, 이전 폭격 미사일의 범위와 아에 겹치지 않을 때 3가지 케이스를 고려하여 기준 범위를 계속 변경하면 된다. 제일 처음 비교할 기준 범위가 필요하기에 초기 기준 범위는 [-1, 100000001]로 설정한다. 이때 주의할 점은 반드시 targets 값을 시작점 기준으로 오름차순 정렬해준다.

• 범위 안에 있을 때 : 기준 범위를 현재 폭격 미사일의 범위로 변경한다.
• 범위가 겹칠 때 : 기준 범위의 시작점을 현재 폭격 미사일의 시작점으로 변경하고 끝점은 그대로 유지한다.
• 범위가 겹치지 않을 때 : 기준 범위를 현재 폭격 미사일의 범위로 변경하고 요격 미사일 수를 증가시킨다.

targets는 1이상으로 폭격 미사일은 1개 이상이기 때문에 answer을 1로 시작한다.

소스 코드

function solution(targets) {
  let answer = 1; // targets는 1이상으로 항상 요격 미사일은 1개 이상 필요
  let [S, E] = [-1, 100000001]; // 기준 범위
    
  targets.sort((a, b) => a[0] - b[0]); // 시작점 기준 오름차순
    
  for (const [s, e] of targets) {
    if (S <= s && E >= e) {
      // 범위 안에 있을 때
      [S, E] = [s, e]; 
    } else if (s < E && e > E) {
      // 범위가 겹칠 때
      [S, E] = [s, E];
    } else {
      // 범위가 겹치지 않을 때
      answer += 1;
      [S, E] = [s, e];
    }
  }
    
  return answer;
}