프로그래머스 : 단속카메라 C++

programmers.co.kr/learn/courses/30/lessons/42884#

코딩테스트 연습 - 단속카메라

 

풀이

1. 일단 시작지점을 오른차순으로 정렬한다!

 -> 최소점이랑 비교해가면서 차근차근 겹치는 여부 판단하면 된다

 

2. while 문을 만들고 탈출 조건은 모든 자동차를 감시한 상태!

 -> visited[i] ==1 이라는건 

 

3. 아직 감시 안된 자동차의 경우

 -> 출발점이 기존 최소값 이상, 최대값 이하일때

 -> 도착점이 기존 최대값 이하, 최솟값 이상일떄

업데이트 하곻 visited 처리

 

4. 루프 한번 돌때마다 answer++

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

bool cmp(vector<int> a, vector<int> b)
{
    return a[0]<b[0];
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    int visited[10001]={0,};
    int flag,min,max;
    
    sort(routes.begin(),routes.end(),cmp);
    while(true)
    {
        flag=1;
        for(int i=0;i<routes.size();i++)
            if(visited[i]==0)//하나라도 카메라 안만난게 있으면
                flag=0;
        if(flag==1)
            break;
        
        min = -98765;
        max = 98765;
        for(int i=0;i<routes.size();i++)
        {
            if(visited[i]==0)
            {
                if(routes[i][0]>=min && routes[i][0]<=max)
                {
                    min = routes[i][0];
                    visited[i]=1;
                }
                
                if(routes[i][1]<=max && routes[i][1]>=min)
                {
                    max = routes[i][1];
                    visited[i]=1;
                }
            }
        }
        
        answer++;
    }
    return answer;
}