[프로그래머스 단속카메라] c++ (코드, 풀이)

문제 링크

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

프로그래머스

 

문제

 

코드 풀이

아직까지는 정답률이 높은순서대로 풀어서 그런지 level3가 풀만하다고는 느끼지만.. 점점 풀다보면 힘들어지겠죠..?

 

잡설은 그만하고 이 문제는 그리디 알고리즘을 요구하는 문제로 최적의 해를 찾아야 하는 문제입니다.

 

이 문제에서 저는 우선 시작점을 기준으로 sort를 하고 그다음 만약에 시작점이 같다면 끝점이 낮은 것을 앞으로 sort를 진행해주었습니다.

위의  방식으로 처음 location을 -30001로 잡아준후

시작지점이 location보다 클때 (3번 케이스) 에 대해서는 location을 갱신과 answer++

아닐경우

끝지점이 기존보다 클 경우 (1번 케이스) 현상유지

끝지점이 기존보다 작을 경우 (2번케이스) location값만 수정

 

을 방식으로 진행하였습니다.

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

bool compare(vector<int> &a, vector<int> & b){

    if(a[0] != b[0])

    {

        return a[0] < b[0];

    }

    return a[1] < b[1];

}

int solution(vector<vector<int>> routes) {

    int answer = 0;

    int location = -30001; // 위치 기준으로 만약 그것 범위 내라면 바로 스킵

   

    sort(routes.begin(),routes.end(),compare);

   

    for(int i = 0; i < routes.size();i++){

        //3번케이스

        if(routes[i][0] > location){

            location = routes[i][1];

            answer++;

        }else{

            //2번케이스

            if(routes[i][1] <= location)

                location = routes[i][1];

            //1번케이스는 location값 유지.

        }

    }

    return answer;

}