[프로그래머스 lv2] 요격 시스템 JS [그리디]

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

 

A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

---

제한 사항

• 1 ≤ targets의 길이 ≤ 500,000
• targets의 각 행은 [s,e] 형태입니다.
  • 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
  • 0 ≤ s < e ≤ 100,000,000

 

 

---

나의 풀이

 

문제정리

• (s, e)만 가능하다. s,e는 포함하지 않는다
• s, e사이 실수 가능
• 최소 미사일 갯수

생각

• 시작점 오름차순으로 정리한다.
• 이전까지 겹치는구간의 마지막(prevEnd)과 현재구간의 시작(currStart)만 비교하면 된다
• targets의 첫번째 구간의 마지막을 prevEnd로 초기화하고 두번째 구간부터 순회하며 prevEnd와 겹치는지 비교한다.
  • prevEnd > currStart이면 겹치므로 겹친구간을 찾고 prevEnd를 갱신한다.
  • 겹치지 않으면 미사일 갯수++하고 prevEnd를 현재구간의 마지막 점으로 갱신한다
• 순회가 끝나고 마지막 미사일을 추가한다 +1

 

겹치는 구간 찾기

a, b 두 구간이 있을 때 a의 끝점 > b의 시작점 (a[1] > b[0]) 이면 겹친다

겹치는 구간은 2가지 경우가 있다

첫번째는 b[0]~a[1]&nbsp; &nbsp; 두번째는 b[0] ~ b[1] 구간이 겹친다

 

function solution(targets) {
  var answer = 0;
  targets.sort((a, b) => a[0] - b[0]);
  let prevEnd = targets[0][1];

  for (let i = 1; i < targets.length; i++) {
    const [currStart, currEnd] = targets[i];
    // 겹침
    if (prevEnd > currStart) {
      prevEnd = Math.min(prevEnd, currEnd); // 현재까지 겹치는 구간 마지막 점 갱신
    } else {
      answer++;
      prevEnd = currEnd;
    }
  }
  return answer + 1; // 마지막 미사일
}

 

느낀점

- 여러 가지 풀이 방법이 있는데 코드를 더 이해하기 쉽게하기 위해 몇 번 고쳤다.

배운점

- 겹치는 구간은 위 그림처럼 2종류가 있다

- 이전까지 겹치는 구간의 마지막 점과 새로운 구간의 시작점을 비교하면 몇개가 겹치는지 알 수 있다. 즉 구간의 시작, 끝점을 둘다 기억할 필요없이 prevEnd, currStart만으로 겹치는지 판단 가능하다.

- 시작점으로 내림차순 한 뒤 뒤에서 순회할 수도 있다.

- 순회 완료 후 마지막 미사일 추가 까먹지 말자

 

---

 

또다른 풀이

타겟의 시작점이 요격 범위의 끝점보다 작으면 요격 가능하다

1. 타겟들의 끝점을 기준으로 오름차순 정렬한다
2. 요격 범위는 끝점만 저장한다
3. 요격 범위의 끝점보다 타겟의 시작점이 작은 경우, 요격 가능
4. 요격 범위의 끝점보다 타겟의 시작점이 큰 경우, 요격 미사일이 하나 더 필요하고 요격 범위 끝점을 타겟의 끝점으로 변경

function solution(targets) {
    //타겟의 끝점을 기준으로 오름차순 정렬
    targets.sort((a, b) => a[1] - b[1]);
    let missile = 0;
    let count = 0;
    
    targets.forEach(([start, end]) => {
        // 타겟의 시작점이 요격범위 끝점보다 크거나 같으면 미사일 추가하고 범위조정
        if (start >= missile) {
            count++;
            missile = end;
        }
    })
    return count;
}