[Programmers] Lv2. 요격 시스템 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

기존에 작성했던 코드랑 새로 작성한 코드랑 전혀 다른 점이 없는 것 같은데, 새로 작성한 코드는 맞았습니다. 무슨 차이인 거지... 제가 푼 방식은 다음과 같습니다.

 

• 미사일들의 start 지점을 기준으로 오름차순 정렬합니다. (start 지점이 같다면, end가 작은 걸로)
• 현재 구간의 마지막 부분(currentEnd)이 미사일의 시작 부분과 같거나 크다면, 현재 구간에선 요격할 수 없는 미사일입니다.
  • 따라서, 새 구간을 늘리고, 현재 미사일의 마지막 부분을 currentEnd로 설정해줍니다.
• 위와 달리 요격할 수 있는 미사일이라면, currentEnd와 미사일의 end 중 작은 걸 currentEnd로 갱신해줍니다.

 

✏️소스 코드 및 결과

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

bool Compare(const vector<int>& m1, const vector<int>& m2) {
    if (m1[0] == m2[0])
        return m1[1] < m2[1];
    return m1[0] < m2[0];
}

int solution(vector<vector<int>> targets) {
    sort(targets.begin(), targets.end(), Compare);
    int currentEnd = 0, answer = 0;

    for (const auto& target : targets) {
        int start = target[0], end = target[1];

        if (currentEnd <= start) {
            answer++;
            currentEnd = end;
            continue;
        }
        
        currentEnd = min(currentEnd, end);
    }
    
    return answer;
}