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

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

 

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

프로그래머스

---

 

 

해결전략

 

탐욕법. 그리디 Greedy Algorithm

 

회의실 배정

---

 

 

정답 코드

 

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

bool Compare(const vector<int>& a, const vector<int>& b)
{
    if (a[1] == b[1])  // e가 같을 경우 s순서로 정렬 (이 부분 생략가능)
        return a[0] < b[0];
    return a[1] < b[1]; // e를 기준으로 오름차순 정렬
}

int solution(vector<vector<int>> tg) {
    int n = tg.size();

    sort(tg.begin(), tg.end(), Compare);

    int answer = 0; // 미사일 수
    int last = -1;  // 마지막으로 e를 저장
    for (int i = 0; i < n; i++)
    {
        if (tg[i][0] < last) continue; // 현재 s가 마지막으로 선택된 e보다 작으면 건너뛴다
        
        last = tg[i][1]; // 마지막으로 선택된 e를 갱신한다.
        answer++; 		 // 미사일 수를 증가시킨다.
    }

    return answer;
}

int main(){
    vector<vector<int>> testcase1 = { {4,5},{4,8},{10,14},{11,13},{5,12},{3,7},{1,4} };
    vector<vector<int>> testcase2 = { {0, 4} ,{1, 2},{1, 3},{3, 4} };
    vector<vector<int>> testcase3 = { {0, 4} ,{0, 1},{2, 3} };

    cout << solution(testcase1) << "\n"; // 3
    cout << solution(testcase2) << "\n"; // 2
    cout << solution(testcase3) << "\n"; // 2

    return 0;
}

 

 

---

 

유사 문제

 

2023.09.06 - [⭐ 코딩테스트/프로그래머스] - [프로그래머스 C++] 호텔 대실

2023.06.21 - [⭐ 코딩테스트/백준] - [백준 1931번 C/C++] 회의실 배정

 

 

---