23.04.21 파이썬 코딩 퀴즈#232 요격 시스템 (프로그래머스 스쿨)

이번 문제는 요격 시스템 문제이다.

문제의 핵심은 미사일을 최소로 사용하여 모든 폭격 미사일을 요격하는 것이다.

A 나라가 발사한 폭격 미사일은 x축에 평행산 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s,e) 형태로 표현된다.

B 나라는 특정 x좌표에 y축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한번에 요걱 가능하다. 하지만 개구간(s, e)로 표현되는 미사일은 s와 e에서 발사하는 요격 미사일로 요격할 수 없습니다.

 

설명만 놓고 봐서는 무슨 말인지 감이 잡히지 않는다.

위 그림설명을 보니, 다시 글 설명이 이해가 된다.

먼저 targets 을 그림으로 나타내면 위와 같아지는데, 이때 개구간 안에서만 요격 가능하다. 개구간이랑 해당 실수값 초과, 미만의 구간을 뜻하기 때문이다.

위 그리메서는 4번에서 쏘면 4개의 미사일을 격추 가능하지만, 4는 개구간이기 때문에 해당 지점에서는 요격할 수 없다.

만약 4번 위치에서 요격한다고 가정하면, [1,4], [4,5],[4,8]은 요격하지 못하고 [3.7] 하나만 요격 가능하다.

코드는 굉장히 단순하다.

앞전에 풀었던 단속카메라 문제와 같은 유형이다.

https://yorysis.tistory.com/324

 

가장 먼저 해야할 일은 targets 의 오름차순 정렬이다. 즉 가장 먼저 위치한 targets부터 미사일을 쏘기 시작하면 된다.

시작전 미사일의 위치는 정렬된 targets[0][0] -1, 첫번째 target 의 발사 직전의 시점이다.

그리고 이제 반복문을 돌면서 미사일과 target의 시작지점을 비교하면 된다.

개구간을 염려해서 해당 문제를 풀게되면 굉장히 코드가 복잡해 진다.

단순하게 현재 미사일의 위치가 targets[i][0] 보다 작거나 같은 경우라면 미사일이 추가로 필요하고, 그 다음 미사일은 현재 targets[i][1] 끝나는 지점에 배치하게 된다.

 

입출력 예를 위 코드로 실행시키면, 

처음 시작시 missle 의 위치는 0 에 있다.

그리고 반복문을 통해 [1,4]를 만나게 되고, 시작 위치가 1, 현재 missle 위치가 0 이므로 추가 미사일을 설치하고(answer + 1) 다음 미사일은 4에 위치하게 된다.

그 다음 만나는건 [3,7] 이다. 조건에 맞지 않기 때문 다음 [4,5] 로 넘어가게 된다.

현재 미사일 위치와 [4,5]는 동일하기 때문에 추가로 미사일을 설치하고 미사일은 5 위치에 놓이게 된다.

그 다음은 [4,8] 이고, 조건에 맞지 않기 때문에 다음인 [5,12]로 넘어간다.

역시 추가로 미사일을 설치하고, 미사일은 12에 놓게 된다.

그리고 남은 미사일들은 조건에 맞지 않기 때문에 추가 설치 없이 종료된다.