[프로그래머스 Lv2] 요격 시스템 - Javascript 풀이

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

프로그래머스

---

문제

폭격 미사일을 요격하기 위해 필요한 요격 미사일의 최소 개수를 구하는 문제

 

생각

그리디 알고리즘을 떠올렸다.

그리디 알고리즘을 사용하기 위해서는 '매 순간의 최선이 전체 최선으로 이어짐'이 성립해야 한다.

 

이 문제는,

끝지점이 빠른 미사일부터 처리하면, 남은 미사일을 최대한 덮을 수 있다.

따라서 전체적으로 필요한 요격의 수를 최소화할 수 있다.

 

완전 탐색으로 풀려면, 모든 구간 조합을 고려해 가장 효율적인 요격 지점을 찾아야 한다.
하지만 이런 방식은 조합 폭발로 인해 시간 복잡도가 급격히 증가하므로, 현실적으로 불가능한 풀이가 된다.

 

문제풀이

먼저, 각 폭격 미사일의 끝 지점(e)을 기준으로 오름차순 정렬한다.
가장 빨리 끝나는 미사일부터 처리해야, 이후 미사일들과의 겹침을 최대화할 수 있기 때문이다.

 

그 다음, 순차적으로 각 폭격 구간을 확인하면서
현재 요격 지점(shot)보다 시작점(s)이 큰 경우,
이전 요격으로는 해당 미사일을 막을 수 없으므로
새로운 요격이 필요하다.

 

따라서 요격의 수(answer)를 1 증가시키고,
shot을 현재 구간의 끝 지점 이전 지점으로 갱신한다.

(이 문제는 개구간 (s, e)이므로, 실제로는 e 바로 이전 지점에서 요격해야 한다.)

---

 

정렬과 요격 로직이 잘 동작하는지 직접 구간별로 확인해보자.
각 단계마다 shot의 위치가 어떻게 변하고, 어떤 구간이 요격되는지 표로 정리했다.

이 과정을 통해

“끝지점 기준 정렬 후, 시작점이 shot보다 큰 구간만 새로 요격한다”는

그리디 로직이 실제로 잘 적용되는 것을 확인할 수 있다.

 

구간 [1, 4]를 지날 때 - shot = 3.9

shot	구간	요격 여부
3.9	[1, 4]	O
	[4, 5]
3.9	[3, 7]	O
	[4, 8]
	[5, 12]
	[11, 13]
	[10, 14]

 

구간 [4, 5]를 지날 때 - shot = 4.9

shot	구간	요격 여부
3.9	[1, 4]	O
4.9	[4, 5]	O
3.9	[3, 7]	O
4.9	[4, 8]	O
	[5, 12]
	[11, 13]
	[10, 14]

 

구간 [5, 12]를 지날 때 - shot = 11.9

shot	구간	요격 여부
3.9	[1, 4]	O
4.9	[4, 5]	O
3.9	[3, 7]	O
4.9	[4, 8]	O
11.9	[5, 12]	O
11.9	[11, 13]	O
11.9	[10, 14]	O

 

코드

function solution(targets) {
    let shot = -1
    let answer = 0
    
    targets.sort((a, b) => a[1]-b[1])
    
    targets.forEach((target, idx) => {
        if ( target[0] > shot ) {
            shot = target[1] - 1
            answer++
        }
    })
    
    return answer
}