programmers.co.kr 코딩테스트 연습 > 연습문제 > 요격 시스템

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스의 단속카메라 문제와 같은 카테고리의 문제입니다.

미사일을 발사한다고 표현하지만, 사실은 X 축과 평행인 직선을 미사일로 표현한 것입니다.

직선에는 시작점과 끝나는 점이 있구요, 2개 이상의 직선이 있다면, 두 직선이 모두 지나가는 구간을 찾을 수 있습니다.

두 직선이 모두 지나가는 구간에서 요격미사일을 발사하면, 2개의 미사일 모두를 격추할 수 있습니다.

문제를 푸는데 중요한 문구를 가지고 왔습니다.

• 개구간 (s,e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 

이 문제에서는 직선의 구간이 개구간입니다. exclusive 라고도 표현합니다.

이 부분이 ‘단속 카메라' 문제와 다른 부분입니다.

한 예를 들어보면, 2개의 직선이 있고, 시작점, 끝점이 [1, 2], [2, 3] 라고 하면,

2개의 직선은 모두 지나가는 구간은 없습니다. 따라서, 2개의 마시일로 격추해야 합니다.

2에서 발사한 요격 미사일은 2개의 폭격 미사일 둘다에 맞지 않습니다.

다른 예로, 2개의 직선의 시작점, 끝점이 [1, 3], [2, 4] 라고 한다면,

아래 구간을 2개의 직선 모두 지나갑니다.

2 < 구간 < 3

부등호에 = 이 없다는 점이 중요한 포인트 입니다.

• 요격 미사일은 실수인 X 좌표에서도 발사할 수 있습니다.

즉 2보다 큰 2.x 같은 실수 에서 발사하여 2개의 폭격 미사일을 1개의 요격 미사일로 격추할 수 있습니다.

한개의 폭격 미사일, 즉, 직선의 시작과 끝을 [s, e] 로 표현합니다.

문제에서 폭격 미사일은 개구간으로 정의 했기 때문에, s와 e가 같은 경우가 있다면,

그 폭격 미사일은 요격할 수 없으므로, s와 e는 같은 경우가 없다고 가정하고 풀었습니다.

최소의 요격 미사일을 사용하려면, 각 폭격 미사일의 s, e의, s 에 따라서 정렬하고,
s 값이 서로 같으면, e 값에 따라서, targets를 정렬해야 합니다.

구간이 겹치는지 확인이 끝난 폭격 미사일을 저장할 리스트 answers 가 필요합니다.

2개의 폭격 미사일이 겹치는 구간이 있는지 체크하고, 있으면 overlapped 변수에 True로 저장합니다.

from typing import List

def solution(targets: List[List]):
    targets.sort()
    answers: List = [targets[0]]
    targets.pop(0)

    for s, e in targets:
        s_prev, e_prev = answers.pop()
        overlapped: bool = False

        if s == s_prev or e == e_prev:
            overlapped = True
        elif s < e_prev < e:
            overlapped = True
        elif s_prev < e < e_prev:
            overlapped = True

        if overlapped:
            answers.append([max(s, s_prev), min(e, e_prev)])
        else:
            answers.append([s_prev, e_prev])
            answers.append([s, e])

    return len(answers)