프로그래머스 - 징검다리 건너기

leehyunjon·2022년 5월 12일

Algorithm

목록 보기

29/162

징검다리 건너기 : https://programmers.co.kr/learn/courses/30/lessons/64062#

Problem

Solve

슬라이딩 윈도으로 해결하려했으나 시간초과로 탈락.
슬라이딩 윈도우를 했을 경우 시간복잡도가 O(K*(N-K))가 되기 때문에 stones탐색 200000, 슬라이딩 윈도우 100000일때 O(20000000000)으로 시간초과가 날수밖에 없다.

결국 이분탐색을 쓰는 방법을 사용했다.(복잡도가 1억이 넘는 터무니 없는 수가 나온다면, 이분탐색이나 dp 등과 같은 방법을 떠올려보라고 어떤 글에서 본것 같다)

이 문제에서 이분탐색의 핵심은 이분탐색으로 사용할 조건을 건널수 있는 사람으로 캐치하는 것인것 같다.
그것만 캐치하면 이분탐색을 사용해서 이분탐색 O(lgN), 배열탐색 O(N)으로 O(NlgN)이 가능해진다(N범위 200000, 건널수 있는 사람 최대 수 200000000)

문제 풀이는 아래와 같다.

이분탐색에서 front를 최소 인원 1, end를 최대 인원 2억으로 초기화.
mid = (front+end)/2로 임시 건널수 있는 인원수를 만든다.
해당 mid에서 건널수 있는지 여부를 확인하고 건널수 있다면 front=mid+1로, 건널수 없다면 end=mid-1로 갱신하여 front<=end일때까지 반복하여 건널수 있는 최대의 인원수를 반환한다.

Code

class Solution {
    public int solution(int[] stones, int k) {
        
        //최소 인원
        int front=1;
        //최대 인원
        int end=200000000;
        int answer = 0;
        
        //이분탐색
        while(front<=end){
        	//임시 건널수 있는 인원
            int mid = (front+end)/2;
            
            if(crossRiver(mid, k, stones)){
            	//건널수 있다면 현재 건널수 있는 인원을 갱신
                answer = Math.max(answer, mid);
                front = mid+1;
            }else{
                end = mid-1;
            }
        }
        
        return answer;
    }
    
    //현재 인원으로 다리를 건널수 있는지 여부 판단
    boolean crossRiver(int user, int k, int[] stones){
    	//건널수 없는 다리 개수
        int count=0;
        
        for(int stone : stones){
        	//현재 다리를 건널수 있는 사용자가 더 많다면 count++
            if(stone-user < 0){
                count++;
            }else{
            //현재 다리를 건널수 있다면 건널수 없는 다리가 연속이 되어야 하므로 count=0으로 갱신.
                count=0;
            }
            
            //건널수 없는 다리가 k만큼있다면 더이상 건널수 없다.
            //count==k라는 것은 건널수 없는 다리 count가 연속으로 k개 만큼 있다는 뜻이다.
            if(count == k){
                return false;
            }
        }
        return true;
    }
}