[프로그래머스 level_4] 징검다리 for JAVA

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

코딩테스트 연습 - 징검다리

[문제 설명]

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치	각 바위 사이의 거리	거리의 최솟값
[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

 

[풀이]

distance의 거리는 10억 이하, 바위 개수는 5만 개 이하다. 제거할 바위에 따른 각 바위 사이의 거리를 구하고 최솟값까지 구하면 분명 효율적인 측면에서 해결할 수 없을 것이다.

 

결국 "거리의 최솟값"을 찾는 문제이고, 주로 답의 형태가 주어진 경우와 계산해야 할 데이터 양이 많을 때는 이분 탐색을 사용하게 된다.

 

 

일단 쉬운 부분부터 접근해보자. 

 

1. 바위들이 정리가 안 되어있으니 정렬해준다.

결국 첫 번째 요소와 마지막 요소는 0과 distance와의 거리를 구해야 한다. 이를 편하게 해 주기 위해 index 0번에 0을, index 마지막에 distance를 추가해주고 정렬해주자.

 

2. 이분 탐색의 기준의 될 "거리의 최솟값"의 범위를 구하는 것이다.

0 ~ distance가 "거리의 최솟값"의 범위가 될 것이다.

 

3. 범위를 좁히는 기준인데, 이 부분이 나는 어려웠다.

"거리의 최솟값"이라는 것은 각 바위마다의 거리들 중 가장 최솟값이 되는 것을 말한다. 우리는 "거리의 최솟값"을 정해놓고 문제풀이를 시작했다. 그러므로 각 바위 사이의 거리가 거리의 최솟값보다 적으면 안 된다는 말이다.

 

그렇다면, 바위 사이의 거리가 미리 정해둔 "거리의 최솟값"보다 작으면 어떻게 해야 할까?

-> 뿌셔야 한다. 일단 답정너인 문제 특성상 바위마다의 거리가 "거리의 최솟값" 이상이어야 한다.

 

바위 사이의 거리가 "거리의 최솟값"보다 클 경우에는 어떻게 해야 할까?

-> 그다음 바위끼리 거리 값을 구한다.

 

4. 뿌셔진 개수로 "거리의 최솟값"의 범위를 정한다.

breakIt(뿌신 개수)가 N보다 작은 경우, 같은 경우, 큰 경우가 있다. 이 경우의 수들은 두 가지로 나뉘는데,

 

1) breakIt <= N

뿌신 개수가 N보다 같다는 말은 문제의 조건에 부합하다는 말이다. 하지만, 더 큰 "거리의 최솟값"중 문제의 조건에 부합하는 경우가 있을 수도 있다. 범위를 오른쪽으로 좁혀준다.

 

뿌신 개수가 N보다 작은 경우, 나머지 바위들이 조건에 부합한다는 말이다. 그러면 우리는 아무 돌이나 뿌셔 N개와 같게 만들 수 있다. 결국 이 경우도 범위를 오른쪽으로 좁혀준다.

 

추가로 breakIt <= N에서 답(answer)을 업데이트해주어야 한다.

 

2) breakIt > N

breakIt(뿌신 개수)가 N보다 더 많다는 말은, "거리의 최솟값이" 너무 커서 "거리의 최솟값"보다 작은 거리를 가진 바위들은 몽따 다 뿌셨다는 말이다. "거리의 최솟값"이 너무 크다! 범위를 왼쪽으로 좁혀준다.

 

 

[코드]

     public int solution(int distance, int[] rocks, int n) {
         int[] rock = new int[rocks.length + 2]; 
         rock[0] = 0;
         rock[rock.length-1] = distance;
         System.arraycopy(rocks, 0, rock, 1, rocks.length);        //1번 : rocks 배열 복사
         
         Arrays.sort(rock);
         
         int right = distance;                                    //2번
         int left = 0;
         int mid = 0;                                            //거리의 최솟값
         int answer = 0;                                        //답
             
         while(left <= right) {                                    //이분 탐색
             mid = (right + left) / 2;
             int breakIt = 0;
             
             int i = 0;
             int j = 1;
             for(int k = 0; k < rock.length -1; k++) {
                 if(rock[j] - rock[i] < mid) {                //3번 :거리의 최솟값보다 작으면 안되므로 뿌시기
                     breakIt++;
                     j++;
                 }else {
                     i = j;
                     j++;
                 }
                 if(breakIt > n) {                            //중간에 뿌신 개수가 n보다 클 경우 break
                     break;
                 }
             }
             
             if(breakIt <= n) {                                //4번
                 left = mid + 1;
                 answer = Math.max(answer, mid);
             }else {
                 right = mid - 1;
             }
             
         }
         return answer;
         
     }

태스트 케이스 통과

느낀 점: 처음에는 어떻게 풀지 몰랐는데, 다른 분의 아이디어를 잠깐 보고 나만의 방식대로 생각해봤다. 그리고 생각대로 구현해봤다. 내가 좀 더 발전해야 되는 방향이 있다면, 문제를 더 체계적으로 생각할 수 있는 사람인 것 같다.