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

jonghyukLee·2022년 9월 23일
0

이번에 풀어본 문제는
프로그래머스 징검다리 건너기 입니다.

📕 문제 링크

❗️코드

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

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

            if (isPossible(stones, k, mid)) {
                answer = Math.max(answer, mid);
                min = mid + 1;
            }
            else {
                max = mid - 1;
            }
        }
        return answer;
    }
    static boolean isPossible(int [] stones, int k, int friends) {
        int cnt = 0;
        for (int stone : stones) {
            if ((stone - friends) < 0) {
                cnt++;
                if (cnt == k) return false;
            }
            else {
                cnt = 0;
            }
        }
        return true;
    }
}

📝 풀이

징검다리를 이룬 돌들은, 한번 밟고 지나갈때 마다 숫자 1씩 감소합니다. 숫자가 0인 돌은 밟고 지나갈 수 없지만, 최대 k만큼 0인 돌을 건너뛸 수 있습니다.
위 조건에 맞게 징검다리를 건너갈 수 있는 최대 인원 수를 구하는 문제입니다.
이분탐색의 중간값은 인원 수를 의미하며, 가능한 최댓값을 탐색하여 구해줄 수 있습니다.

📜 후기

이게 왜 레벨 3이지? 하고 풀었다가, 효율성 다 틀렸습니다..ㅋㅋㅋㅋ 입력값의 범위를 보고 이분탐색을 고려해야 하는건지, 틀리고 깨닫는게 맞는건지 궁금하네요 ㅠ

profile
머무르지 않기!

0개의 댓글