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

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

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

2021-03-03

---

import java.util.Arrays;
 
public class Solution64062 {
    public static boolean check(int mid, int[] stones, int k) {
        int count = 0;
        for (int stone : stones) {
            if (stone - mid < 0) count++;
            else count = 0;
 
            if (count == k) return false;
        }
        return true;
    }
    public static int solution(int[] stones, int k) {
        int answer = 0;
        int start = Arrays.stream(stones).min().getAsInt();
        int end = Arrays.stream(stones).max().getAsInt();
 
        if(start == end) return end;
 
        while(start <= end) {
            int mid = (start + end) >> 1;
            if(check(mid, stones, k)) {
                start = mid + 1;
                answer = mid;
            } else end = mid - 1;
        }
 
        return answer;
    }
    public static void main(String[] args) {
        int[] s = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
        int k = 3;
 
        System.out.println(solution(s, k));
    }
}

 

#문제풀이

맨처음에 완전 잘못 생각해서 이상한 방법?으로 접근 했다가 틀리고, 파라매트릭 서치를 이용하여 풀었다.

 

1. 디딤돌 숫자의 가장 최소값(start)과 최대값(end)을 구한다. 그냥 단순하게 for문으로 구하려다가, stream으로 구하는 방법이 있다고 해서 써봤다.

 

2. 만약 start와 end값이 같다면, 모든 디딤돌의 숫자가 같은 것이므로 start(end)의 값이 답이 된다.

 

3. 그렇지 않은 경우, 이분탐색을 해주어야한다. 이 때 기준은 건널 수 있는 친구가 몇 명인지이다.

예를 들어, 3명((1+5) >> 1)이 건널 수 있다고 가정해본다. 그렇다면, 3명 이하(1~3)는 모두 건널 수 있는 친구의 숫자이다. 하지만 최대가 아닐 수도 있으므로, 3명 초과(4,5)도 체크해봐야한다. 

 

4. 그리고 건널 수 있는지 체크하고 싶은 친구의 수를 이용하여, check함수에서 건널 수 있는지 체크했다.

디딤돌 숫자 - 체크할 친구의 수를 해주면서, 음수가 나오는 경우를 count 해봤을 때 주어딘 k값과 같으면 건너는 것이 불가능한 경우라고 체크했다.

 

+) 이 때, 음수가 아니라 0보다 작거나 같은으로 조건을 잘못줘서, 제출했을 때 거의 다 틀렸었다. 

조금 더 꼼꼼히 체크 하는 습관을 가져야할 것 같다,,