[프로그래머스] 단속카메라 (C++, Java)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42884?language=java 

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

1. 주의할 점

- 정렬 기준을 선택한다

- 정렬기준에 따라 더 나은(? 짧은) 방법을 선택한다

 

2. 구현

- 차량의 끝지점을 기준으로 오름차순 정렬을 한다. 같다면, 시작점의 오름차순으로 정렬한다

- 우선순위큐를 사용하여 각 차량의 구간을 정렬한다

- 1개 뽑은 이후, 이 구간의 가장 오른쪽 끝부분(Right)과 우선순위큐에서 뽑아내는 원소의 가장 왼쪽부분(Cl)을 비교한다

- Right < Cl라면 새로운 구간이 생겨나므로 단속카메라를 추가해야한다. 또한, Right를 뽑아낸 원소의 가장 오른쪽 부분인 Cr로 교체한다

- 이외의 경우라면 겹치는 구간이 존재하므로 무시한다

 

[C++]

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
struct info{
    int start,end;
};
struct cmp{
    bool operator()(info &a, info &b){
        if(a.end==b.end){
            return a.start > b.start;
        }
        else return a.end > b.end;
    }
};

int solution(vector<vector<int>> routes) {
    int answer = 0;
    priority_queue<info,vector<info>,cmp> pq;
    for(int i=0;i<routes.size();i++){
        pq.push({routes[i][0],routes[i][1]});
    }
    answer++;
    int left = pq.top().start;
    int right = pq.top().end;
    pq.pop();
    while(!pq.empty()){
        int cl = pq.top().start;
        int cr = pq.top().end;
        pq.pop();
        if(right<cl){       //새로운 단속
            answer++;
            right = cr;
        }
    }
    return answer;
}

 

[Java]

import java.util.*;
import java.io.*;

class Solution {
    public class Info implements Comparable<Info>{
        int start,end;
        public Info(int start, int end){
            this.start=start;
            this.end=end;
        }
        @Override
        public int compareTo(Info o){
            return Integer.compare(this.end,o.end);
        }
    }
    public int solution(int[][] routes) {
        int answer = 0;
        PriorityQueue<Info> pq = new PriorityQueue<>();
        for(int i=0;i<routes.length;i++){
            pq.offer(new Info(routes[i][0],routes[i][1]));
        }
        Info ii = pq.poll();
        int right = ii.end;
        answer++;
        while(!pq.isEmpty()){
            ii = pq.poll();
            int cl = ii.start;
            int cr = ii.end;
            if(right<cl){
                right = cr;
                answer++;
            }
        }
        return answer;
    }
}