[프로그래머스] 징검다리 건너기 (자바)

 

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

프로그래머스

 

 

아래의 조건 때문에 완전탐색은 불가능하다고 판단했다.

• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.

그럼 DP 나 이분탐색을 사용해야 겠다고 생각했다. 

- DP: DP를 적용해도 시간 복잡도 단축이 크지 않을 것 같았다. 최악의 경우 stones의 원소 값만큼 시간복잡도가 깊어질 수 있기 때문에..

- 이분탐색: 위의 이유로 이분탐색을 적용해야 겠다는 삘이 왔다.. 하지만 어떻게 적용해야 할지 감을 못 잡았다. 그래서 다른 분들 풀이를 참고했다.

 

left와 right를 사람 수의 min과 max로 잡으면 풀이가 가능했다.

 

 

class Solution {
    static int[] stones;
    static int k;
    
    public int solution(int[] stones, int k) {
        this.stones = stones;
        this.k = k;
        
        int answer = 0;
        int min = 1; 
        int max = 200000000;
	      
        while (min <= max) {
            int mid = (min + max) / 2;
            
            if (isPossible(mid)) {
                min = mid + 1;
                answer = Math.max(answer, mid);
            } else {
                max = mid - 1;
            }
        }
        
        return answer;
    }
    
    boolean isPossible(int friends) {
      	int skip = 0;
        
        for (int stone : stones) {
            if (stone - friends < 0) {
                skip++;
            }
            else {
                skip = 0;
            }
            
            if (skip == k) {
                return false;
            }
        }
        
        return true;
    }
}

 

 

 

left와 right는 거리 또는 위치를 기준으로 잡아야 한다는 생각이 있었던 것 같다..

 

[느낀점]

이분탐색을 할 때 left, right, mid는 꼭 거리나 위치가 아니어도 된다.

시간복잡도를 올리는 원인이 되는 값을 left, right, mid로 잡는 경우도 고려하자.

(이 문제에서는 사람 수를 left, right, mid로 잡았다.)