[그리디] 단속카메라 - Java코드 (프로그래머스 버그존재)

 

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

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

 

문제

 

항상 느끼는건데 문제가 참 상냥하지 못함.

+ 이번에는 문제 설명에 이상한점이 있음,

입출력의 설명 부분에서 -5, -15 지점을 지난다는 말은 틀린말이 아니지만, 사람들에게 혼동을 줄 수 있는 말들임

 

로직상 통과하는 부분에 카메라를 설치해주어야 최소값을 찾을수 있을것으로 보인다.

올바른 로직으로 구현했을때 카메라는

제일 먼저 빠져나가는 3번 차량의 -13에서 카메라가 설치되어 1번, 2번 을 같이 찍고,

그외에 포함되지않는 4번차량의 범위내에 한번더 설치되어 총 2개가 설치되어야 한다.

 

문제 설명이 항상 불친절한데, 잘못된 이해를 할 수밖에 없도록 만든다.

이상한 로직을 만들게 하는... 프로그래머스...

근데 풀고 제출하다보니 버그가 있었다.. (부들부들... 아래 설명할 예정)

 

 

설계

진입순서는 중요하지않다. 고속도로를 빠져나가는 순서대로 정렬해서

가장 먼저 빠져나가는 차량부분에서  카메라 설치를 시작하고,

해당 부분보다 먼저 진입한 차들은 카메라를 모두 지나갈때니 걸러주다가,

차량 진입시점이 카메라 설치시점보다 큰 경우 Count를 해주면서 카메라를 설치해주는 지점으로 설정하면 된다.  

 

포인트

배열 객체에 대한 사용자 정렬,

그리디한 비교 설계

 

풀이

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    	public int solution(int[][] routes) {
		// 시작점 기준으로 정렬
		Arrays.sort(routes, (a,b)->{
			return a[1]-b[1];
		});
		int ans=1;
		int next=routes[0][1]; //카메라 설치부분
		for(int i=1;i<routes.length;i++) {
			if(routes[i][0]>=next) {
				ans++;
				next=routes[i][1];
			}
		}
		return ans;
	}
}

효율성 하나가 걸려서 미치는줄 알았다. 

시간초과도 아니고 메모리를 많이 사용한것도 아닌데...

왜 걸린건지 참나... 56mb 면 지극히 정상범위 같은데..

 

일단,

정렬부분부터 비교해보면서 다른 방식으로 정렬해보았다.

// Comparator의 재정의
Arrays.sort(routes, new Comparator<int []>() {
	@Override
		public int compare(int[] o1, int[] o2) {
		return o1[1] - o2[1];
	}
});	
		

// 람다식을 이용한 정의
Arrays.sort(routes, (a,b)->{
	return a[1]-b[1]
});


// 람다식에서 return 없이 Integer.compare()를 이용한 정의
Arrays.sort(routes, (a,b)-> Integer.compare(a[1], b[1]));

걍 똑같다. 람다식을 간결하게 이용할수록 시간과 메모리를 아주 조금씩 적게 먹긴하는데,

사실 거의 똑같다.. 

뭐지ㅜㅜ

 

그냥 다른 사람의 풀이를 찾아 제출해서 얼마나 효율적인지 비교해봐야겠다.

 

다른사람의 풀이

import java.util.Arrays;
class Solution {
	public int solution(int[][] routes) {
		Arrays.sort(routes, (a,b)-> Integer.compare(a[1], b[1]));
		int cnt = 0;	
		int min = Integer.MIN_VALUE;
		for(int[] route : routes) {
			if(min <  route[0] ) {
				min = route[1];
				cnt++;
			}
		}
        return cnt;
    }
}

엥?

내 풀이 보다 무려 3ms나 더걸렸고,2MB 더 먹었는데,

 

똑같은 로직인데 왜 이분은 통과고 나는 통과 안시켜줌?

프로그래머스 화나게 하네...