Codility NailingPlanks; Java

https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/

NailingPlanks coding task - Learn to Code - Codility

import java.util.Arrays;

class Solution {
    public int minNails(int plankStart, int plankEnd, int[][] sortedC, int prev) {
		int start = 0, end = sortedC.length-1, mid = 0;
		
		int minIdx = -1;	//조건 만족하기 시작하는 nail idx
		while(start<=end) {
			mid = (start+end)/2;
			
			if(sortedC[mid][0] < plankStart) {
				start = mid + 1;
			}else if(sortedC[mid][0] > plankEnd) {
				end = mid - 1;
			}else {
				minIdx = mid;
				end = mid - 1;
			}
		}
		//조건 만족하는 nail이 없다
		if(minIdx == -1) {
			return -1;
		}
		
		int minOrgIdx = sortedC[minIdx][1];
		for(int i=minIdx;i<sortedC.length;i++) {
			if(sortedC[i][0] > plankEnd)	break;
			minOrgIdx = Math.min(sortedC[i][1], minOrgIdx);
			if(minOrgIdx<=prev) {
				return prev;
			}
		}
		
		return minOrgIdx;
	}
	public int solution(int[] A, int[] B, int[] C) {
        // Implement your solution here
		int N = A.length;
		int M = C.length;
		int k = 0;	//current idx of Array A, B
		
		int[][] sortedC = new int[M][2];
		for(int i=0;i<M;i++) {
			sortedC[i][0] = C[i];
			sortedC[i][1] = i;
		}
        Arrays.sort(sortedC, (c1, c2)->{
			return c1[0] - c2[0];
		});
		
		//한 널빤지의 못 사용 최소 개수 구하기 
		int result = 0, numberOfNails = 0;
		for(int i=0;i<N;i++) {
			numberOfNails = minNails(A[i], B[i], sortedC, result);
			if(numberOfNails == -1)		return -1;
			result = Math.max(result, numberOfNails);
		}
		return result + 1;
    }
}

어떻게 binary search를 하라는 건지 모르겠어서.. 검색해서 코드 보고 익혔다. nail=못, plank=널빤지 ^^

 

1. 못을 원래 인덱스를 살리면서 정렬해준다.

1-1. sortedC[i][0]: C[i] 값 / sortedC[i][1]: 원래 C에서의 인덱스 순서 값, 즉 i

 

2. 널빤지 하나씩 탐색하며 이 널빤지의 못 사용 최소 개수를 구한다. => minNails 함수

sortedC를 binary search해서 조건에 맞는(A[k]~B[k]인 C[i]) 못의 시작 인덱스(minIdx)를 구한다.

minIdx부터 sortedC를 탐색해서 못 중 원래 인덱스의 최솟값(minOrgIdx)을 구한다.

 

* 이때, 여태까지 구했던 최소 인덱스 값보다 지금 구한 값이 더 작으면 여태까지 구했던 최소 인덱스 값을 리턴하고 계산을 끝낸다. 

이 부분이 처음에 이해가 안 되었다. 왜 구하다 말지? 했는데 시간 아끼려고 더 구하지 않는 것이었다. 어차피 구해봤자 solution함수에서 max를 구하니까 가 이유다.

 

3. 못 사용 최소 개수 중 최대가 정답

* 이 부분이 왜 최대인지 처음에는 이해가 되지 않았다. 정답은 최소 못의 구하는 것이기 때문이다. 최대 못의 값을 구하려고 최대값을 구하는 게 아니라, 모든 널빤지의 못 사용 개수를 고려해주어야 하기 때문이다. 각 널빤지의 못 사용 개수(minNails함수의 리턴 값)가 이미 최소 사용 개수이기 때문에 모든 널빤지의 못 사용 개수의 최대를 구해준다.

 

 

- result

참고로 소요 시간은 2시간 30분이다^^ㅜ.. 

https://app.codility.com/demo/results/trainingYY4S7D-QPZ/

Test results - Codility