[프로그래머스] 요격시스템 (C++)

개요

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

개인적인 체감 난이도는 BOJ 기준 S3-S4 언저리 정도 되는 듯 하다.

 

접근

범위를 정렬 후 그리디 형태로 풀면 될 듯 했다.

이전 미사일의 범위를 넘어갈 경우 카운트를 증가시킨다.

그 후 범위를 넘어간 범위로 재설정 하면 될 것이라고 판단했다.

 

한 번 틀렸다.

이전 미사일 범위의 끝점(e)보다 현재 끝점(e)가 작은 경우 해당 범위를 이전 미사일 범위로 바꾸어주어야 했다.

그렇지 않을 경우 아래와 같은 결과가 나오게 된다.(답:2, 실출력:1)

 

풀이

1. 미사일 범위를 오름차순 정렬한다.

2. 반복문으로 미사일의 범위들(targets)을 탐색한다.

3. 마지막 미사일 범위의 e(lastE)를 s가 넘으면 answer++하고 lastE를 e로 바꾼다.

4. 넘지 않았을 때 lastE보다 e가 작으면 laseE를 e로 바꾼다.

 

주의

1. 입력이 오름차순으로 주어지지 않는다.

2. 모든 미사일의 범위는 개구간(열린구간)이므로 s와 e는 포함되지 않는다.

코드

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

int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(), targets.end());
    
    int lastE = 0;
    for(const auto& t : targets)
    {
        int s = t[0];
        int e = t[1];
        
        if(s >= lastE)
        {
            lastE = e;
            answer++;
        }
        else if(e <= lastE)
        {
            lastE = e;
        }
    }
    return answer;
}