[프로그래머스/level2/JS] 요격 시스템

문제링크

[프로그래머스/level2/JS] 요격 시스템

 

 

문제설명

A나라에서 B나라로 미사일을 쏠 때, B나라에서 방어를 위해 날아오는 미사일을 요격할 때 최소한의 미사일의 개수를 구하는 문제이다. 이때 B미사일은 A미사일을 요격할 때 통과할 수 있으며 A나라, B나라의 세계는 2차원 공간의 세상이다.

 

2차원 공간의 세상이라는 것이 이해가 잘 안갈 수 있는데 밑의 그림을 보면 조금 더 쉽게 이해할 수 있다.

 

2차원 공간의 미사일

 

A나라에서 날아오는 미사일의 두께가 빨간색 선이고 B나라에서 발사하는 위치는 X선 상의 좌표와 같다. 이때 B가 발사하는 좌표는 실수이며 빨간색 선의 구간은 개구간으로 이루어진다. 개구간은 각 좌표를 포함하지 않는, 그러니까 (3, 5)라고 하면 3초과, 5미만의 구간이다. 예를 들어 A에서 발사한 미사일이 (1,4), (4,7)로 날아올 때 B나라에서 4의 좌표에서 미사일을 발사하면 사이로 가서 요격을 못한다는 이야기이다. 두발 다 맞음

 

제한 사항은

1. 1 <= targets <= 500,000

2. targets의 각 행은 [s, e]로 이루어져있고 이는 개구간 (s, e)로 날아온다는 것을 의미한다. 0 <= s  < e <= 1,000,000,000

 

미사일은 최대 10^5 * 5개가 날아오고 좌표는 10^9개인 것이다. 완전탐색으로 모든 미사일에 대해서 모든 좌표를 비교한다면 시간초과가 날 뿐 아니라 최소한의 미사일을 개수를 구하기가 어려워진다.

 

그렇다면 어떻게 접근해야할까?

 

우선 모든 미사일을 적어도 한발은 맞추어야한다. 그리고 최소 미사일의 개수를 구하는 것이므로 앞의 미사일을 맞추면서 최대한 뒤의 미사일까지 맞추어야한다. 그렇다면 정렬을 통해 시작 X좌표가 작고 구간이 작은 미사일부터 정렬한 후 미사일을 쏘는 것으로 생각하면 어떨까? 그렇게 생각한다면 문제는 제법 단순해진다.

 

 

1번 미사일이 제일 앞의 미사일이라면 비내림차순으로 정렬이 되어있으므로 그 다음에 오는 미사일의 유형은 2, 3, 4 세가지가 있다.

 

1번의 경우에는 제일 앞의 미사일이므로 아무 곳이나 맞추면 된다. 현재 임시로 발사할 미사일 좌표를 구간의 끝으로 맞추어 두면 2번 미사일을 같이 요격하면서, 4번과 같이 끝 구간을 넘는 미사일이 올 때 다음 미사일을 발사할 지 비교할 수 있다. 

2번의 경우에는 1번에서 구간의 끝 부분을 맞추는 것으로 했으므로 같이 요격된다.

3번의 경우에는 3번 미사일의 구간을 맞추어야 1번 미사일과 같이 요격된다. 그러므로 현재 미사일 좌표를 3번 구간의 끝으로 변경해야 한다.

4번 미사일의 경우에는 같이 요격할 수 없다. 그러므로 새로운 미사일을 발사해야한다.

 

1번 미사일을 요격할 때 2, 3, 4 미사일의 유형을 고려해주면서 어느 좌표로 미사일을 쏠 지 결정하면 쉽게 문제를 해결할 수 있다.

 

코드

function solution(targets) {
    let answer = 0;
    
    // A미사일 범위 비내림차순 정렬
    targets.sort((a, b) => a[0] - b[0] || a[1] - b[1]); 
    
    // 현재 쏠 것으로 예상되는 미사일의 좌표
    let currentFire = -1;
    
    targets.forEach(([start, end]) => {
        if(start >= currentFire) {
	        // 현재 미사일의 좌표가 다음 미사일 구간의 시작보다 작다면 => 4번 케이스
            currentFire = end; // 현재 미사일의 좌표를 다음 미사일 구간의 끝부분으로.
            answer++; // 미사일 1개 증가
        } else if (end < currentFire) {
        	// 다음 미사일 구간의 끝부분이 현재 미사일 좌표보다 작다면 => 3번 케이스
            currentFire = end; // 현재 미사일 좌표를 3번 케이스의 좌표로.
        }
        
        // 2번 케이스에서는 현재 좌표로 발사하면 요격되므로 처리해주지 않는다.
    })
    
    return answer;
}

 

읽어주셔서 감사합니다.

문제를 발견하시거나 궁금한 점이 있으면 댓글로 알려주세요!