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

06 Jun 2023 in Develop on C++, Algorithm Last modified at: 2023-06-08

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

프로그래머스 : 요격 시스템(링크)

알고리즘

1. 구현
2. 라인스위핑
3. 정렬

풀이

1. 이차원 벡터를 cmp 함수를 이용해서 두번째 요소를 기준으로 정렬한다
2. 라인 스위핑을 이용해서 iterator를 옮겨가며 문제 기준에 맞는지 확인한다
3. 미사일 개수만큼 반복한다

코드

#include <bits/stdc++.h>

using namespace std;

bool cmp (vector<int> &a, vector<int> &b)
{
    if(a[1] == b[1]) return a[0] < b[0];
    else return a[1] < b[1];
}

int solution(vector<vector<int>> targets) {
    int answer = 1;
   
    sort(targets.begin(), targets.end(), cmp);
    
    int from = targets[0][0];
    int to = targets[0][1];
    
    for(int i = 1; i< targets.size(); i++)
    {
        if(targets[i][0] < to) continue;
        from = targets[i][0];
        to = targets[i][1];
        answer++;
    }
    
    return answer;
}

평가

• 이차원 벡터의 커스텀 정렬에 대해 이해하고, 라인스위핑에 풀이법에 대해 이해한다

참고 : 풀이-GitHub링크