프로그래머스 단속카메라 자바 - peulogeulaemeoseu dansogkamela jaba

<풀이>

일단 문제는 어렵지 않게 접근을 했는데 진입 지점을 기준으로 오름차순 정렬 하는게 아니라 진출 지점 기준으로 오름차순 정렬을 해야한다니!! 정렬을 바꾸니 바로 통과가 되드라,,

​

문제에 나와있는 예시로 설명을 하자면

1. 진출 지점을 기준으로 오름차순 정렬한다.

[-20, -15]

[-18, -13]

[-14, -5]

[-5, -3]

2. -15 보다 진입 지점이 작다면 같은 카메라를 사용한다!

next는 i번째 바로 다음을 체크 하므로 next = i + 1;

while(next < routes.length && routes[next][0] <= routes[i][1]){

next++;

}

-15보다 작거나 같을 때까지 패스해준다.

3. 모두 패스해줬다면 다음 인덱스 i는 next - 1로 초기화 해준다.

4. 반복문이 종료 될 때 까지 위 과정을 반복한다.

​

결국 진출지점보다 작은 진입 지점들은 같은 카메라로 간주하는것이다.

👁‍🗨 단속카메라

그림을 그려가면서 생각해보면 쉽게 해결할 수 있는 문제이다. 

문제 설명

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

고속도로를 이동하는 차량의 경로 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]]	6

🔑 IDEA

나는 주어진 배열을 진입 지점 기준으로 오름차순 정렬하였다.

그리고 카메라 위치는 진출 지점 기준으로 생각한다. 

처음 커서 위치(camera)는 배열의 0번 째 요소의 진출 지점으로 설정한다. 

(즉시 카메라를 설치하지는 않는다.) 

하얀색을 현재 차량, 노란색을 다음 차량이라고 생각할 때, 

위와 같은 세 가지 케이스로 나눠볼 수 있다. 

1. 다음 차량의 진출지점이 커서 위치보다 작으면, 커서를 다음 차량의 진출지점으로 옮긴다. 
2. 다음 차량의 진입지점이 커서위치 이하이고 진출지점이 커서 위치 이상이면, 커서를 그대로 둔다. 
3. 다음 차량의 진입지점이 커서 위치보다 크면, 커서 위치에 카메라를 설치하고 커서를 다음 차량 진출지점으로 옮긴다.

💡  나의 풀이

import java.util.*; class Solution { public int solution(int[][] routes) { Arrays.sort(routes, (int[] o1, int[] o2) -> o1[0] - o2[0]); int num = 0; int cam = routes[0][1]; for(int i=1; i<routes.length; i++) { if(routes[i][1] < cam) cam = routes[i][1]; if(routes[i][0] > cam) { cam = routes[i][1]; num++; } } return num+1; } }

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

[[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2

programmers.co.kr

문제 설명

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

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

제한사항

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

입출력 예

routesreturn

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

입출력 예 설명

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

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

• solution.cpp

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

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

[[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2

programmers.co.kr

문제

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

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

입출력의 설명 부분에서 -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 더 먹었는데,

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

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