[Lv.3] 징검다리 건너기 : Java

프로그래머스

 

 

 

이해하기

나한테 가중치 有 → DFS 풀이 라서 DFS 문제인가? 했지만 효율성을 따진다는 점에서 아마 DFS로 풀었으면 시간초과가 떴을 것...

 

이번에 참고한 블로그는 요기⬇️

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

 

• 이진탐색으로 풀이할 것!
• min = 0명
• max = Integer.MAX_VALUE

 

문제풀이

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;

        int min = 0;
        int max = Integer.MAX_VALUE;

        while (min <= max) {
            int mid = (min + max) / 2;

            if (check(mid, k, stones)) {
                min = mid + 1;
                answer = mid;
            } else {
                max = mid - 1;
            }
        }

        return answer;
    }

    public boolean check(int mid, int k, int[] stones) {
        int count = 0;

        for (int i = 0; i < stones.length; i++) {
            if (stones[i] < mid) {
                count++;
                if (count >= k) {
                    return false;
                }
            } else {
                count = 0;
            }
        }

        return true;
    }
}

 

        int min = 0;
        int max = Integer.MAX_VALUE;

 

min과 max 초기화

 

        while (min <= max) {
            int mid = (min + max) / 2;

 

min이 max보다 커진다면 while문 종료

mid = (min + max) / 2

 

            if (check(mid, k, stones)) {
                min = mid + 1;
                answer = mid;
            } else {
                max = mid - 1;
            }

 

유효한 값인지 check하여 만약 mid까지 전부 건너는 것이 가능하다면 min을 mid + 1로 높여주고 answer에 일단 min 저장

유효하지않다면 수를 줄여야하니 max = mid - 1

 

    public boolean check(int mid, int k, int[] stones) {
        int count = 0;

 

check 함수에는 count 변수를 만들어주고

 

        for (int i = 0; i < stones.length; i++) {
            if (stones[i] < mid) {
                count++;
                if (count >= k) {
                    return false;
                }

 

stone[i]가 mid보다 작다면 mid가 디딜 수 없다는 뜻이니 count++해준다. 

count는 디딜 수 없는 돌(뛰어 넘어야 하는 돌)의 개수이다.

 

만약 count가 k와 같거나 커진다면 (사실 같다면으로 해도 될 것 같음) return false해주는데,

난 이 부분이 왜 count > k 가 아니라 count >= k인지 궁금했다.

 

이 부분에 대해서는 요 블로그 참고⬇️

 

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

연속해서 건너지 못하는 개수(한 번에 뛰어 넘어야 하는 개수)가 늘어나면 다음 사람이 건너지 못하기 때문에 바로 반환하는 것이라고 한다.

 

            } else {
                count = 0;
            }

 

만약 stones[i]가 mid보다 크거나 작다면 else문 내를 실행한다.

이 때 count = 0은 이미 건넜으니 다음 계산을 위해 디딜 수 없는 돌의 개수를 초기화해주는 것이다.

 

 

  

이진탐색은 항상 보고 나면 쉬운데 떠올리기가 어려운 것 같다.

이진탐색 문제를 좀 더 풀어봐야지