프로그래머스(단속카메라)

import java.util.*;
class route implements Comparable<route>{
    int a;
    int b;
    int c;
    public route(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
    @Override
    public int compareTo(route r) {
        if(a < r.a)
            return -1;
        else if(a > r.a)
            return 1;
        else {
            if(c < r.c)
                return -1;
            else if(c > r.c)
                return 1;
            else 
                return 0;
        }
    }
}

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        List<route> list = new ArrayList<>();
        for(int i = 0; i<routes.length;++i) {
            list.add(new route(routes[i][0],i, 0));
            list.add(new route(routes[i][1],i, 1));
        }
        
        Collections.sort(list);
        //Queue<route> stack = new LinkedList<>();
        //int min = list.get(0).a;
        //int max = list.get(list.size()-1).a;
        //stack.add(list.get(0));
        int minC = -30001;
        for(int i = 0; i<list.size();++i) {
            route t = list.get(i);
            if(t.c == 1) {
                if(minC < routes[t.b][0]) {
                    answer++;
                    minC = t.a;
                }
            }
        }
        // c             d
        //-20 1 0, -18 3 0, -14 2 0, -13 3 1, -5 4 0, -5 2 1, -3 4 1, 15 1 1
        
        //들어온 뒤에 처음 나가는 것이 있을 경우 카메라를 놓는다.
        //나간 것이 존재하고 이후에 값이 들어올 경우, 
        return answer;
    }
}

 

취업한 이후로 블로그 쓰고 싶지 않았는데.. 계속 했어야 했다.

스터디 책에서 그리디 알고리즘이 나왔으므로 관련 문제를 올려본다.

키 포인트는 카메라를 두는 조건을 명확히 설정을 하고 이에 맞춰 코딩을 해야 한다.

일단 차량이 들어오고 나가는 각 시점을 시간 순으로 정렬을 해야겠다 싶어서 이를 따로 쪼개 list에 넣고 정렬을 했다.

차량 진출시점의 최소값이 -30000이었기 때문에 우선 카메라 위치의 min 값으로 -30001을 잡았고

for문을 돌리면서 list 내의 객체가 out일 때(c==1) 마지막 카메라의 위치가 차가 진입한 시점보다 이전이면 나갈때 카메라를 하나 세워주는 식으로 진행했다. 차량의 inout을 시간순으로 정렬했기 때문에 마지막 카메라 위치만 알면 되니까 값을 따로 기억하지는 않고 마지막 카메라 위치만 체크해서 풀면 꽤 간단했다.