프로그래머스 [연습문제 / 요격 시스템](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 181188 요격 시스템

---

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

문제 설명:

A 나라가 발사한 폭격 미사일들을 최소한의 요격 미사일로 모두 요격하는 문제입니다. 각 폭격 미사일은 개구간 (s, e) 형태로 x축에 평행하게 날아오며, 특정 x 좌표에서 요격 미사일을 발사하면 해당 좌표를 지나는 모든 폭격 미사일을 한 번에 요격할 수 있습니다. 개구간이므로 s와 e 위치에서는 요격이 불가능합니다. 최소 요격 미사일 개수를 구해야 합니다.

---

문제 해결 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 1;  // 최소 1개의 요격 미사일은 필요
    
    // 끝점 기준 오름차순 정렬 (시작점은 두 번째 정렬 기준)
    sort(targets.begin(), targets.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[1] != b[1]) {
            return a[1] < b[1];  // 끝점 기준 오름차순
        }
        return a[0] < b[0];      // 끝점이 같으면 시작점 기준
    });
    
    // 현재 요격 미사일로 커버 가능한 최대 x 좌표
    int interceptPoint = targets[0][1];
    
    // 모든 미사일을 순회하며 요격 가능 여부 확인
    for (int i = 1; i < targets.size(); i++) {
        int currentStart = targets[i][0];
        int currentEnd = targets[i][1];
        
        // 현재 미사일의 시작점이 요격 지점 이상이면 새로운 요격 필요
        if (interceptPoint <= currentStart) {
            answer++;
            interceptPoint = currentEnd;  // 새로운 요격 지점 설정
        }
        // 현재 미사일의 끝점이 더 작으면 요격 지점 갱신
        else if (currentEnd < interceptPoint) {
            interceptPoint = currentEnd;
        }
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 그리디 알고리즘과 정렬을 활용한 구간 스케줄링 문제입니다. 끝점을 기준으로 정렬한 후, 각 미사일을 순회하며 현재 요격 지점으로 커버 가능한지 확인합니다. 커버할 수 없는 미사일이 나타나면 새로운 요격 미사일을 추가하고, 커버 가능하면 요격 지점을 최적화합니다.
• 구현 세부사항:
  • 끝점 기준 오름차순 정렬: 빨리 끝나는 미사일부터 처리하여 최대한 많은 미사일을 한 번에 커버합니다.
  • interceptPoint 변수로 현재 요격 가능한 최대 x 좌표를 추적합니다.
  • 개구간이므로 interceptPoint ≤ currentStart 조건일 때 새로운 요격이 필요합니다.
  • currentEnd가 더 작으면 요격 지점을 갱신하여 더 많은 미사일을 커버할 가능성을 높입니다.
  • priority_queue 대신 sort와 람다 함수를 사용하여 코드를 간소화했습니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n log n)으로 정렬에 소요되는 시간이 지배적입니다. 이후 선형 탐색은 O(n)입니다. 공간 복잡도는 O(1)로 추가 공간을 거의 사용하지 않습니다 (정렬은 in-place).

---

실행 예시

입력:

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

실행 과정:

• 끝점 기준 정렬: [[1,4], [4,5], [3,7], [4,8], [5,12], [11,13], [10,14]]
• interceptPoint = 4 (첫 번째 미사일 [1,4]의 끝점)
• [4,5]: 시작점 4 ≥ interceptPoint 4 → 새로운 요격 필요 (answer=2, interceptPoint=5)
• [3,7]: 시작점 3 < 5, 끝점 7 → interceptPoint 유지
• [4,8]: 시작점 4 < 5, 끝점 8 → interceptPoint 유지
• [5,12]: 시작점 5 ≥ 5 → 새로운 요격 필요 (answer=3, interceptPoint=12)
• [11,13]: 시작점 11 < 12, 끝점 13 → interceptPoint 유지
• [10,14]: 시작점 10 < 12, 끝점 14 → interceptPoint 유지

출력:

3

---

결과

그리디 알고리즘의 전형적인 구간 스케줄링 문제로, 끝점 기준 정렬과 요격 지점 추적을 통해 최소 요격 미사일 개수를 효율적으로 계산했습니다. LG전자 코딩테스트에 출제된 유형으로, 유사 문제들에 적용 가능한 핵심 패턴입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!