[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기

• 문제 - programmers.co.kr/learn/courses/30/lessons/64062

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

 

• 분석

처음에 문제 해결을 위해 '디딤돌의 숫자가 연속해서 K번 0이 되는 구간이 발생하는 경우'를 구하려고 했었다. 하지만 이 방식은 완전탐색으로 이어졌고, 효율성 측면에서 실패할 수 밖에 없었다. 결과적으로 풀이를 참고하였고, [이분탐색]을 활용해 문제를 풀 수 있었다. 

 

풀이를 참고하며 놀랐던 점은 이분탐색을 적용하는 기준이 '징검다리를 건넌 니니즈 친구들의 수'였다는 것이다. 나는 단순히 디딤돌의 숫자에 초점을 맞춰 징검다리를 건널 수 있는 니니즈 친구들의 수를 구하려고 했었기 때문이다. 

class Solution {
    public int solution(int[] stones, int k) {
        int front = 1;
        int back = getMaxElement(stones);
        
        while(front <= back) {
        	int mid = (front + back) / 2;
        	
        	if(binarySearch(stones, mid, k)) {
            	// mid 숫자만큼 건널 수 있으므로 그보다 작은 수에 대해 탐색을 위함
        		back = mid - 1;
        	}
        	else {
            	// mid 숫자만큼 건널 수 없으므로 그보다 큰 수에 대해 탐색을 위함
        		front = mid + 1;
        	}
        }
        
        return front;
    }
	
    // 최대값 구하기
    private static int getMaxElement(int[] stones) {
    	int len = stones.length;
        int maxVal = 0;
		
        for(int index = 0; index < len; index++) {
        	maxVal = Math.max(maxVal, stones[index]);
        }
		
        return maxVal;
    }
	
    // 이분탐색
    private static boolean binarySearch(int[] stones, int mid, int k) {
    	int cnt = 0;
        int len = stones.length;
		
        for(int index = 0; index < len; index++) {
        	if(stones[index] - mid <= 0) {
            	// 0이 되는 구간이 k이상인 경우
            	if(++cnt >= k) {
                	return true;
                }
            }
            else {
            	cnt = 0;
            }
        }
		
        return false;
    }
}