프로그래머스 요격 시스템 Python

프로그래머스 문제: 요격 시스템 (Python)

문제

● 문제 설명

A 나라가 B 나라의 군사 기지를 폭격하기 위해 폭격 미사일을 발사합니다. B 나라에는 이를 막기 위한 요격 시스템이 존재하는데, 이 시스템은 특정한 방식으로 작동합니다.

1. A 나라의 폭격 미사일은 x축에 평행한 직선 구간으로 날아갑니다.
   • 이때 각 미사일은 (s, e)라는 두 점으로 표현됩니다.
   • (s, e)는 개구간입니다. 즉, s와 e에서는 요격이 불가능하고, 그 사이 구간에서만 요격 가능합니다.
2. B 나라의 요격 미사일은 수직으로 발사됩니다.
   • 어떤 특정한 x 좌표에서 발사하면, 그 x 값을 포함하는 모든 (s, e) 구간을 동시에 요격합니다.
   • 다시 말해, s < x < e인 경우에만 해당 미사일을 요격할 수 있습니다.
3. 문제의 목표는 다음과 같습니다.
   • 모든 (s, e) 구간을 커버하기 위해 필요한 최소한의 요격 미사일 개수를 구하는 것입니다.

● 제한 사항

• 1 ≤ targets의 길이 ≤ 500,000
• 0 ≤ s < e ≤ 100,000,000
• targets[i] = [s, e]
• 요격 미사일은 정수 좌표뿐만 아니라 실수 좌표에서도 발사할 수 있습니다.

● 테스트 케이스

입력	출력
[[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]	3

● 문제 작동 원리

⚠️ 시작 전 전제: 문제의 구조 다시 보기

• A 나라 미사일 → x축 (s, e) 구간으로 날아갑니다.
• B 나라 요격 미사일 → 특정 x 좌표에서 위로 발사되어, 그 좌표가 포함된 모든 (s, e) 구간을 한 번에 요격합니다.
• 중요한 조건: (s, e)는 개구간이므로, 시작점 s와 끝점 e에서는 요격할 수 없습니다.

즉, 목표는 최소한의 요격 미사일 발사로 모든 (s, e) 구간을 커버하는 것입니다.

📘 요격 시스템 문제: 실제 문제 해결 흐름

⚠️ 시작 전 전제: 문제의 구조 다시 보기

• A 나라가 발사한 폭격 미사일은 x축에서 (s, e) 구간으로 날아옵니다.
  • 여기서 (s, e)는 개구간입니다. 즉, s < x < e인 x값에서만 요격이 가능합니다.
• B 나라는 수직으로 요격 미사일을 발사합니다.
  • 이 요격 미사일은 특정 x 좌표에서 위로 쏘아지며, 그 x 값이 포함된 모든 (s, e) 구간을 동시에 요격합니다.
• 목표는 무엇인가요?
  • 모든 (s, e) 구간을 커버하도록 최소한의 요격 미사일을 쏘는 것입니다.

✅ 첫 번째 단계: 모든 미사일 구간을 정렬한다

● 왜 정렬해야 하나요?

1. 지금 우리는 요격 미사일을 어디에 쏴야 할지 결정해야 합니다.
2. 이 결정은 순서를 아무렇게나 보면 절대 불가능합니다.
3. 그래서 먼저 어떤 기준으로 미사일들을 정리(정렬)해야 합니다.

● 어떤 기준으로 정렬하나요?

• 우리는 미사일을 끝나는 x 좌표(e) 기준으로 오름차순 정렬합니다.
• 왜 끝나는 점으로 정렬하나요?

다음과 같이 두 개의 미사일이 있다고 생각해보십시오.

미사일 번호	시작점 s	끝점 e
A	3	10
B	6	7

만약 우리가 A부터 보면, "10 이전 아무 데나 쏘면 되겠네?" 하고 생각할 수 있습니다. 그런데 B는 7 전에 쏴야 합니다. 즉, 더 일찍 끝나는 구간이 먼저 처리되어야, 그 구간에 맞춰 요격 미사일을 쏘면 나중 구간까지 함께 처리할 수도 있습니다.

그래서 우리는 항상 가장 빨리 끝나는 구간부터 확인해야 하며, 그 순서를 만들기 위해 끝점 e 기준 정렬을 합니다.

● 구체적인 예

입력: [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]

정렬 결과:

[ [1,4], [3,7], [4,5], [4,8], [5,12], [11,13], [10,14] ]

끝점이 가장 빠른 순서대로 정렬되었습니다.

✅ 두 번째 단계: 요격 미사일을 쏘기 시작한다

● 요격 미사일을 처음에는 아무것도 쏘지 않은 상태입니다

• 그래서 첫 번째 구간은 반드시 요격 미사일을 새로 쏴야 합니다.
• 이 구간은 (1, 4)입니다.
• 이 구간은 x가 1보다 크고, 4보다 작은 모든 실수에서 요격 가능합니다.
  • 예를 들어 x = 2, x = 3.9999 등

우리는 이 구간을 커버하기 위해, x = 4에 요격 미사일을 쏘는 것으로 결정합니다.

● 잠깐, 왜 x=4인가요?

• (1, 4)를 커버하려면 1 < x < 4인 x를 선택해야 합니다.
• 가장 가까운 지점은 x = 4 - ε입니다. 여기서 ε는 아주 작은 실수입니다.
• 실제 코드에서는 x = 4라고 저장해도 상관없습니다. 중요한 건 4보다 작지만 4에 최대한 가까운 x입니다.

● 첫 번째 요격 미사일 쐈음 → 다음 구간으로 넘어간다

✅ 세 번째 단계: 다음 구간이 기존 요격 미사일로 커버 가능한지 확인한다

● 두 번째 구간: (3, 7)

• 이 구간은 3 < x < 7인 모든 x에서 요격 가능합니다.
• 우리는 방금 x = 4에 요격 미사일을 쐈습니다.
• 그럼, 4는 3 < 4 < 7이므로 이 구간은 요격됩니다.

✅ 이 구간은 이미 요격된 상태입니다 → 새로운 미사일 필요 없음

● 세 번째 구간: (4, 5)

• 4 < x < 5인 x에서만 요격됩니다.
• 현재 요격 미사일 위치는 x = 4
• 하지만 이 구간은 x=4를 포함하지 않습니다.

⚠️ 이 구간은 기존 요격 미사일로 커버되지 않습니다 → 새로운 미사일을 쏴야 합니다

• 우리는 (4,5)에서 미사일을 막아야 하므로, 가장 늦은 시점인 x = 5 - ε에서 쏘는 것이 최선입니다.
• 그래서 두 번째 요격 미사일을 x = 5에 쏘았다고 가정합니다.

● 다음 구간: (4, 8)

• 이 구간은 4 < x < 8
• 현재 요격 미사일 x = 5는 4 < 5 < 8에 해당함

✅ 이 구간은 두 번째 미사일로 커버됨 → 새로 쏠 필요 없음

● 다음 구간: (5, 12)

• 5 < x < 12
• 현재 요격 미사일은 x = 5
• 5는 포함 안 되므로 → 커버 안 됨

⚠️ 새 요격 미사일 필요 → x = 12에 발사

• 하지만 실제로는 (5,12)니까 x = 12 - ε 에 쏘는 것이 최적
• 세 번째 요격 미사일 발사

● 다음 구간: (11,13)

• 11 < x < 13
• 요격 미사일 위치: x = 12
• 11 < 12 < 13 → ✅ 커버됨

● 마지막 구간: (10,14)

• 10 < x < 14
• x = 12 → ✅ 커버됨

✅ 네 번째 단계: 요격 미사일 개수 세기

지금까지 요격 미사일을 쏜 시점은:

1. x = 4
2. x = 5
3. x = 12

따라서 정답은 3개입니다.

✅ 끝까지 절대 요약 없이 정리

순서	구간	요격 미사일 위치	커버 여부	미사일 개수
1	(1,4)	x = 4	❌	+1 → 1
2	(3,7)	x = 4	✅	그대로
3	(4,5)	x = 4 → 안됨	❌	+1 → 2
4	(4,8)	x = 5	✅	그대로
5	(5,12)	x = 5 → 안됨	❌	+1 → 3
6	(11,13)	x = 12	✅	그대로
7	(10,14)	x = 12	✅	그대로

⛳ 결론

• 끝점 기준으로 정렬한다
• 커버 안 되는 구간이 나오면 그 구간의 끝점에 가까운 x에 요격 미사일을 쏜다
• 그 이후 구간들을 다시 그 x로 커버 가능한지 확인한다
• 이걸 반복해서 모든 구간을 커버할 때까지 진행한다
• 커버할 수 없는 구간이 나올 때만 요격 미사일 수를 1 증가시킨다

아이디어

1. 구간들을 끝점 기준으로 정렬한다.
2. 첫 구간에서 미사일을 하나 쏜다.
3. 다음 구간이 현재 쏜 미사일 좌표로 커버되면 그대로 두고, 커버되지 않으면 새로운 미사일을 그 구간 끝점에 맞춰 쏜다.
4. 이 과정을 반복하면 최소 개수로 모든 구간을 커버할 수 있다.

전체 코드

def solution(targets):
    answer = 0
    targets.sort(key=lambda x: x[1])

    curr = -1
    for i in targets:
        if i[0] < curr and i[1] >= curr:
            continue
        else:
            curr = i[1]
            answer += 1
    return answer
    

결론

• 끝점 기준으로 정렬하는 것이 핵심 전략입니다.
• 가장 빨리 끝나는 구간에 맞춰 쏜 미사일이 이후 구간들을 최대한 많이 커버하도록 합니다.
• 커버되지 않는 구간이 나오면 새로운 미사일을 발사해야 하며, 이때는 반드시 해당 구간의 끝점 근처에서 쏘아야 합니다.
• 최종적으로, 테스트 케이스 [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]의 경우 정답은 3입니다.