[프로그래머스][2019 카카오 개발자 겨울 인턴십] 징검다리 건너기

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

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

import java.io.*;
import java.util.*;

class Solution {
	public int solution(int[] stones, int k) {
        int answer = 0;
        int left = 0;
        int right = Arrays.stream(stones).max().getAsInt();
        int mid = 0;
        
        while(left<=right) {
        	mid = (left+right)/2;
        	boolean check = isStepStone(mid, stones, k);
        	
        	//걷널 수 있다면 mid 이상에 못 걷너는 친구가 있다.
        	if(check) {
        		answer = mid;
        		left = mid+1;
        	}else {
        		right = mid-1;
        	}
        }
        
        return answer+1;
    }
	
	private boolean isStepStone(int mid, int[] stones, int k) {
		int[] temp = Arrays.copyOf(stones, stones.length);
		
		// 스톤 제거
		for(int i=0; i<stones.length; i++) {
			temp[i] -= mid;
		}
		
		int index =0;
		
		// k이상 스톤이 비어 있는지 검사
		for(int i=0; i<temp.length; i++) {
			if(temp[i] <= 0) index++;
			else index =0;
			
			if(index == k) return false;
		}
		
		return true;
	}

	public static void main(String[] args) {
		int a = new Solution().solution(new int[] {2, 4, 5, 3, 2, 1, 4, 2, 5, 1}, 3);
		System.out.println(a);
	}
}

정리

연속된 K개의 디딤돌에 적힌 숫자가 모두 0인 구간이 있으면 더 이상 징검다리를 건널 수 없으며, 이를 이용해 이분 탐색하면 문제를 해결할 수 있습니다. 먼저 M번째 친구가 징검다리를 건널 수 있는지 확인하기 위해 M – 1 번째 친구까지 징검다리를 건넌 상황을 구합니다. 이때, M – 1번째 친구까지는 K값에 관계없이 모두 징검다리를 건넜다고 가정합니다. 따라서, 징검다리에 적힌 숫자가 M보다 작다면 숫자가 0이 됐다고 표시해주면 됩니다. 이제 M번째 친구가 징검다리를 건널 수 있는지 확인하기 위해 징검다리에서 0이 연속으로 K개가 나오는 구간이 있는지 확인합니다.

• 0이 연속으로 K개가 나오는 구간이 있는 경우 : M번째 친구는 징검다리를 건널 수 없습니다.
• 또한, M번째 친구보다 뒤에 건너는 친구들은 모두 징검다리를 건널 수 없습니다.
• 따라서 찾아야 하는 답은 0 이상 M – 1 이하인 정수 중 하나입니다.
• 0이 연속으로 K개가 나오는 구간이 없는 경우 : M번째 친구는 징검다리를 건널 수 있습니다.
• 이 경우 첫 번째 ~ M – 1 번째 친구들은 모두 정상적으로 징검다리를 건널 수 있습니다.