[알고리즘] Greedy 활용 ④

지난 글 hjee02018.log - Greedy 활용 ②에 이어 Greedy를 활용한 문제 풀이를 해보도록 한다.

1. 문제 개요

문제 출처 : 프로그래머스 단속카메라 lv3.

1) 문제 정의

2) 제한 사항

3) 입출력 형식

2. Solution

1) 알고리즘

① 진출지점 기준 오름차순 정렬

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

bool cmp(vector<int> &a, vector<int>&b)
{
    return a[1]<b[1];
}
int solution(vector<vector<int>> routes) 
{
    int answer = 0;
    // 진출지점 기준 오름차순
    // 최소 진출 위치에 카메라 설치
    // [[-20,-15], [-18,-13], [-14,-5], [-5,-3]]
    sort(routes.begin(),routes.end(),cmp);
    // 설치된 위치
    answer++;
    int cur=routes[0][1];

② 차량마다 진입 위치가 이전 차량의 진출 위치보다 크다면 카메라 설치 (반복)

int cur=routes[0][1];
    for(int i=1;i<routes.size();i++)
    {
        if(routes[i][0]<=cur)
            continue;
        else
        {
            cur=routes[i][1];
            answer++;
        }
    }

위 문제는 문제 출처 : 프로그래머스 요격시스템 lv2 문제와 거의 동일한 문제로 비교적 쉬운 난이도의 Greedy를 활용한 문제 해결이다.