[알고리즘 문제풀이] 프로그래머스 - 단속카메라

yourjin·2022년 2월 27일

level3 알고리즘 탐욕법(Greedy)

알고리즘 문제풀이

목록 보기

6/28

TIL (2022.02.11)

➕ 오늘 푼 문제

프로그래머스 - 단속카메라

➕ 아이디어

경로를 시작 위치를 기준으로 정렬한다.
이전까지 경로들이 함께 겹쳐지는 구간을 저장하는 변수를 만든다 (start, end)
다음 경로들을 탐색하며
- 이전 경로들과 겹치는 구간이 있다면, 카메라를 설치하지 않고 겹치는 구간만 갱신한다.
- 겹치는 구간이 없다면, 카메라를 새로 설치하고 새로운 구간을 만든다.

➕ Java 코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        int start, end;
        
				// 시작, 종료 위치 기준으로 정렬해준다.
        Arrays.sort(routes, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                if(o1[0] == o2[0]){
                    return o1[1] - o2[1];
                }else{
                    return o1[0] - o2[0];
                }
            } 
        });
        start = routes[0][0];
        end = routes[0][1];
        
        for(int i=1; i<routes.length; i++){
            int s = routes[i][0], e = routes[i][1];
            if(start <= s && s <= end){
								// 겹치는 구간이 있다면, 단속 카메라를 새로 설치하지 않고 구간만 갱신한다.
                start = s;
                end = Math.min(e, end);
            }else{
								// 겹치는 구간이 없다면, 단속 카메라를 새로 설치하고 새로운 구간을 정한다.
                answer += 1;
                start = s;
                end = e;
            }
        }
        return answer;
    }
}

➕ Python 코드

def solution(routes):
    answer = 1
    
	  routes.sort()
    start, end = routes[0][0], routes[0][1]
    
		for s, e in routes:
        if start <= s <= end:
						# 겹치는 구간이 있다면, 단속 카메라를 새로 설치하지 않고 구간만 갱신한다.
            start, end = s, min(e, end)
        else:
						# 겹치는 구간이 없다면, 단속 카메라를 새로 설치하고 새로운 구간을 정한다.
            answer += 1
            start, end = s, e
    return answer