[프로그래머스]징검다리건너기_Java

--문제--

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

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

--문제 접근--

처음에는 그저 하나씩 카운팅 하는 방법을 고려하였지만 효율성면에서 떨어지므로 pass

다음 방법을 고려하여 이분 탐색을 고려하였습니다.

징검다리를 건너는 친구의 수를 기준으로 이분 탐색을 활용했습니다.

 

--코드--

package Level3;

public class 징검다리건너기 {
	//처음엔 그저 하나씩 카운팅 하는 방법을 고려하였지만 그방법은 효율성이 떨어지므로 pass
	//다음 방법인 이분탐색을 사용
	//징검다리를 건너는 친구의 수를 기준으로 이분 탐색을 활용해보는 것.
	public static void main(String[] args) {
		int[] tmp= {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
		System.out.println(solution(tmp,3));
	}

	private static int solution(int[] stones, int k) {
		int answer=0;
		int min=0;
		int max=200000000;
		//이분탐색 과정..
		while(min<=max) {
			int mid=(min+max)/2;
			if(isCross(stones,k,mid)) {
				min=mid+1;
				answer=Math.max(answer, mid);
			}else {
				max=mid-1;
			}
			
		}
		return answer;
	}

	private static boolean isCross(int[] stones, int k, int mid) {
		
		int tmp=0;
		//징검다리를 건널 수 있나 확인하는 과정
		for(int i=0;i<stones.length;i++) {
			if(stones[i]-mid<0) {
				tmp++;
			}else {
				tmp=0;
			}
			//연속으로 못건너는 것이 K라면 못건너는 상황.
			if(tmp==k)return false;
		}		
		
		return true;
	}
}