프로그래머스 그리디, 단속카메라

문제

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

풀이

저번에 풀이를 봤던 디스크 컨트롤러와 비슷한 방식으로 접근하였다. 이 문제를 그리디라고 인식하고 접근하면 쉽게 떠올릴 수 있는 방법인데 그냥 구간의 큰 값(오른쪽 값)이 제일 최소인 것을 찾아 단속카메라를 설치하는 것을 반복하면서 모든 차량이 완료될때까지 하면 된다. 이를 허접한 그림으로 나타내면 아래와 같다. (그림이 뭔가 이상한데 저 구간의 대소관계를 나타낸다고 보면 된다)

이 문제는 모든 차량이 보일 수 있도록 단속카메라를 설치하는 최소의 개수이므로, 오른쪽 값이 최소인 끝 구간을 찾아 거기에 두면서 해당 단속 카메라에 적발되는 차량을 지워나가면 항상 최소인 감시 카메라의 개수를 구할 수 있다. 그리디에서 말하는 현재의 최선의 선택이 최적해가 되는 것임을 생각해보면 이해하기 쉬울 것이다.

다만 구현에서 살짝 실수를 해서 시간초과가 났는데, 처음에는 끝난 것은 삭제를 할까 했다가 그러면 시간초과가 날 것 같아 정렬을 끝난 것은 최대 값을 넣어서 뒤에다 배치하고 맨 앞이 최대가 되면 끝나는 코드를 짯는데 이렇게 하니까 시간초과가 났다... 거의 정렬되어 있는 문제라서 퀵소트가 O(n)이 나오지 않을까 했는데 아닌 것 같다. 그래서 이후에는 처음에만 정렬하고 이후에는 정렬하지 않고 값만 최대 값을(done) 넣어서 done인 경우는 무시하는 코드를 짯다.

실수

• STL 사용이 미숙해서 아직 인터넷을 참고해야함
• 시간복잡도를 제대로 생각하지 않아서 처음에 실수함 (시간초과)
• break을 빼먹어서 거꾸로 정렬해야 정답이 나오던 사태가 발생함
• 이 컨셉을 생각하는데 오랜 시간이 걸림.

코드

틀린 첫번째 코드

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

using namespace std;

#define done 999999

bool compare(vector<int> front, vector<int> back){ // 비교함수 작성
    
    return front[1] < back[1];
    
    
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), compare);
    
    for(; routes[0][1] != done;){
        
        int emplace = routes[0][1];
        
        for(int i = 0; i < routes.size(); i++){
            
            if(routes[i][0] <= emplace && emplace <= routes[i][1]){
                
                routes[i][0] = done;
                routes[i][1] = done;
                
            }
            
        }
        
        sort(routes.begin(), routes.end(), compare);
        
        answer++;
        
        
    }
    
    return answer;
}

맞은 코드

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

using namespace std;

#define done 999999

bool compare(vector<int> front, vector<int> back){ // 비교함수 작성
    
    return front[1] < back[1];
    
    
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), compare);
    
    for(;;){
        
        int emplace = done;
        
        for(int i = 0; i < routes.size(); i++){
            
            if(routes[i][1] != done){
                
                emplace = routes[i][1];
                break; // 여기 빠뜨림
                
            }
            
        }
        
        if(emplace == done)
            break;
        
        for(int i = 0; i < routes.size(); i++){
            
            if(routes[i][0] <= emplace && emplace <= routes[i][1]){
                
                routes[i][0] = done;
                routes[i][1] = done;
                
            }
            
        }
       
        answer++;
        
        
    }
    
    return answer;
}

개선사항

스터디 결과 다른 사람들은 구간의 관계를 통해 중복을 줄이고, 마지막에는 서로 교집합이 없는 포함 관계만 남겨서 계산을 최소로 줄이는 방식을 사용했는데 나같은 경우에는 그렇게 하지 않아서 시간에서 손해를 많이 봤었다. ( log(n^2) 수준)

다만 다른 사람의 코드를 염탐한 결과 나처럼 구간의 마지막을 기준으로 정렬하고, 감시카메라의 마지막 위치를 기억하면서 마지막 감시 카메라의 영역에 포함된다면 고려하지 않고 포함되지 않는다면 해당 구간의 마지막에 새로운 감시 카메라를 설치한다면 O(n)의 시간에 해결이 가능했다. 다음에는 문제를 간단하게 생각하는 것도 좋지만 시간 복잡도도 고려하고 좀더 생각하고 풀어보자.