프로그래머스 섬 연결하기(Level3 Java)

https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=java

프로그래머스

---

문제

문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

차량의 대수는 1대 이상 10,000대 이하입니다.
routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
입출력 예

routes return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2
입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

---

문제 해결을 위한 과정

이 문제의 핵심 아이디어는 진출 지점을 기준으로 생각하는 것입니다.

1. 정렬: 모든 차량의 경로를 나가는 지점을 기준으로 오름차순 정렬합니다. 그 이유는 어떤 차량이 나가는 지점에 카메라를 설치하면, 그 지점보다 앞에서 들어오고 뒤에서 나가는 모든 차량을 가장 효율적으로 단속할 수 있기 때문입니다.
2. 카메라 설치:
   • 첫 번째 차량이 나가는 지점(pos)에 카메라를 설치합니다.
   • 다음 차량들을 순회하며, 차량의 진입 지점(start)이 현재 카메라 위치(pos)보다 뒤에 있다면?
   • 기존 카메라로는 이 차를 잡을 수 없으므로, 새 카메라를 이 차량의 진출 지점에 설치하고 pos를 갱신합니다.
3. 반복: 모든 차량을 확인할 때까지 위 과정을 반복합니다.

---

소스코드

import java.util.*;

class Solution {
    static ArrayList<Info> list = new ArrayList<>();
    
    static class Info implements Comparable<Info> {
        int start;
        int end;
        
        public Info(int start, int end) {
            this.start = start;
            this.end = end;
        }
        
        @Override
        public int compareTo(Info o) {
            return this.end - o.end;
        }
    }
    
    public int solution(int[][] routes) {
        int answer = 0;
        int pos = 0;
        
        for(int i = 0; i < routes.length; i++) {
            int a = routes[i][0];
            int b = routes[i][1];
            
            list.add(new Info(a, b));
        }
        
        Collections.sort(list);
        
        pos = -30001;
        
        for(int i = 0; i < list.size(); i++) {
            if(pos < list.get(i).start) {
                pos = list.get(i).end;
                answer += 1;
            }
        }
        return answer;
    }
}