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

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

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

class Solution {
	    public int solution(int[] stones, int k) {
	        int answer = 0;
	        
	        long left=0; //0명
	        long right = 200000000; //2억명
	        
	        while(left<=right){
	            long mid=(left+right)/2; //건널 수 있는 사람 수를 미드로 두고 바꿀거임
	            
	            if(!play(mid,stones, k)) { //못건넌다면 
	            	right=mid-1;
	            }
	            else { //건널 수 있다면 ?
	            	//Max값 확인
	            	answer = (int)Math.max(answer, mid);
	            	left=mid+1;
	            }
	            
	        }
	         return answer;
	    }

		private boolean play(long mid, int[] stones, int k) {
			int cnt=0;
			for(int i=0; i<stones.length; i++) {
				if(stones[i]-mid<0) {
					if(++cnt==k) return false;
				}
				else cnt=0;
			}
			return true;
		}
	}

소요시간 : 23분

 

문제의 제한사항을 보면 "아 이분 탐색이구나" 생각이 나실 겁니다.

 

일단 이분 탐색을 통해 궁극적으로 구해야 하는 것은 총 몇 명의 사람이 징검다리를 건널 수 있느냐입니다.

 

그렇다면 당연히 mid값을 징검다리를 건널 수 있는 사람으로 설정해야겠죠?

 

우선 stones배열의 원소 값이 1~200,000,000이기 때문에 가장 많은 사람들이 징검다리를 건넌다고 해도 2억 명입니다.

그리고 최솟값은 당연히 1명이겠죠?

 

시간 복잡도를 한번 계산해보면 

사람의 수를 이분 탐색 -> log 200,000,000 -> 약 28입니다.

사람의 수가 mid일 때 건널 수 있는지 없는지 탐색 -> stones배열의 길이가 200,000까지 기 때문에

시간 복잡도는 28*200000 = 약 5,600,000입니다. 충분한 시간이네요

 

그럼 로직을 살펴보겠습니다.

 

1. mid값을 설정한다.

2. 징검다리를 건널 수 있는지 확인한다

3. 최댓값을 저장한다.

 

위의 내용들을 다 이해하셨다면 로직은 쉽게 느껴지실 겁니다.

 

징검다리를 건널 수 있는지 확인하는 방법은

stones배열을 순회하며 mid만큼 -를 해줍니다.

이때 stones배열에서 - 가 k번만큼 반복된다면 이는 건널 수 없다는 뜻입니다!

이렇게 하면 금방 뚝딱 하실 수 있습니다

 

끝~