[프로그래머스42884][C++] 단속카메라

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

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

 

문제

 

해결

사실 프로그래머스는 문제 풀이 유형이 사전에 다 보여서,, 그리디를 활용하여 어떻게 푸는지만 생각하면 된다.

그런데 그리디는 왜이리도 익숙해지지 않는지ㅠㅠ 어려운 유형은 아닌 것 같으면서도 막상 풀려고 하면 못풀겠는 그런,,

 

우선 내가 해결한 방식도 어렵진 않기 때문에 코드부터 보자.

🧨미리 말하자면, 필요없이 길어 그리 좋은 코드는 아닌듯싶다. 밑에 더 간단하고 좋은 코드도 첨부함!

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;

    sort(routes.begin(), routes.end()); // *정렬*

    bool checked[10005] = { 0 };

    for (int i = 0; i < routes.size(); i++) {
        if (checked[i] == true) continue;
        int cura = routes[i][0];
        int curb = routes[i][1];
        for (int j = i + 1; j < routes.size(); j++) {
            if (checked[j] == true) continue;
            int newa = routes[j][0];
            int newb = routes[j][1];
            if ((cura <= newa && newa <= curb) || (cura <= newb && newb <= curb)) {   // 범위 겹치면
                cura = max(cura, newa);
                curb = min(curb, newb);
                checked[i] = true;
                checked[j] = true;
            }
        }
        checked[i] = true;
        answer++;
    }

    return answer;
}

routes의 차를 하나씩 돌면서 이후에 들어오는 차들과 하나씩 비교하며 그 두 개의 차 사이에 겹치는 부분이 있으면 해당하는 차들은 카메라에 찍혔다고 체크하고(checked = ture) 카메라 값을 하나 증가시킨다.

여기서, 처음에 정렬을 안하고 실행시켰더니 다 실패했다. (사실 정확한 이유는 모르겠지만 대충 생각해보면 꼬여서 오류가 날 것 같긴하다..) 아무튼 정렬하면 깔끔하게 순서대로 접근하기 쉽기 때문에 정렬을 하자.

 

내가 생각한 방법은 checked를 활용하는 방법이었는데, 이럴 필요없이 너무 깔끔한 풀이를 찾아서 이것도 공유하고자 한다.

 

// 더 간단한 풀이

int solution2(vector<vector<int>> routes) {
    //기본 카메라 1대
    int answer = 1;
    //들어온 리스트 정렬
    sort(routes.begin(), routes.end());
    //비교를 위해 처음차가 나가는 부분 체크
    int temp = routes[0][1];
    //리스트 순회하기
    for (auto a : routes) {
        //현재 차가 나가는 부분보다 뒤에 차가 들어온다면
        if (temp < a[0]) {
            //카메라 설치
            answer++;
            //나가는 부분 정정
            temp = a[1];
        }
        //현재 차보다 뒤차가 먼저나가면 
        if (temp >= a[1])    temp = a[1];// 나가는 부분을 뒷차로 수정
    }
    return answer;
}

[코드 출처] https://mungto.tistory.com/49

🎈순서대로 정렬한 후 뒷 차가 들어오는 시간이 앞 차가 나가는 시간보다 앞서면 겹치는 것이고, 뒷 차가 들어오는 시간이 앞 차가 나가는 시간 이후이면 겹치지 않는 것이다. 코드가 매우 간단하고 깔끔하다! 나는 더 연습해야겠다,,