쌓고 쌓다

[프로그래머스] 단속카메라 Java 풀이 및 해설 본문

알고리즘/프로그래머스

[프로그래머스] 단속카메라 Java 풀이 및 해설

승민아 2024. 5. 7. 09:06

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이 방법

  • 진출 지점을 기준 오름차순 정렬한다.
    • 다음 차량의 진출 시점은 현재 차량의 진출 시점보다 같거나 크다가 보장된다.
    • 그럼 다음 차량의 진입 시점을 가지고 현재 카메라로 찍을 수 있는지 없는지 판별할 수 있다.
  • 첫 카메라는 첫 차량의 진출 지점에 설치한다.
  • 다음 카메라의 설치 필요는 현재 카메라로 다음 차량의 진입을 찍을 수 없을때 설치한다.

 

전체 코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        Arrays.sort(routes, (o1, o2) -> {
            return o1[1] - o2[1];
        });

        int end = routes[0][1]; // 진출 지점에 카메라 설치
        answer++;
    
        for(int i=1; i<routes.length; i++) {
            if(end < routes[i][0]) { // 다음 자동차의 진입이 현재 카메라 위치보다 크다면 새로운 카메라가 필요함.
                end = routes[i][1];
                answer++;
            }
        }
        
        return answer;
    }
}
Comments