[코테연습] 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=python3

프로그래머스

 

문제타입

• 이진 탐색을 활용한 최적화 문제
• 주어진 제약 조건을 기반으로 최적의 값을 구하는 문제 (최대 횟수 구하기)
• 그리디 알고리즘과 함께 동작하며, 연속된 0이 k개 이상 생기지 않도록 건널 수 있는 횟수를 찾아야 함

문제분석

• stones 배열은 각 돌의 건널 수를 나타냄
• k는 연속된 0의 최대 개수를 의미하며, 연속된 0이 k개 이상일 경우 더 이상 건널 수 없음
• 목표는 최대 몇 번 건널 수 있는지 구하는 것
• 이 문제는 이진 탐색을 사용하여 최대 건널 수를 효율적으로 찾아내는 문제임

문제풀이

• 이진 탐색을 사용하여 가능한 건널 수(x)에 대해 isPossible 함수를 이용하여 해당 x값이 가능한지 확인
• x값이 가능하다면 더 큰 값도 시도할 수 있으므로 left = mid + 1로 범위를 확장
• x값이 불가능하면 범위를 축소하여 더 작은 값을 찾음
• isPossible 함수는 주어진 x 값으로 건너보았을 때, 연속된 0이 k개 이상 생기지 않으면 true, 그렇지 않으면 false를 반환
• 최종적으로 가능한 x값 중 가장 큰 값을 구함

 

> java

 

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;  // 최종 결과를 저장할 변수

        int left = 1;  // 건널 수 있는 최소 횟수
        int right = Integer.MAX_VALUE;  // 건널 수 있는 최대 횟수, 매우 큰 값으로 설정

        // 이진 탐색 시작
        while (left <= right) {
            int mid = (left + right) / 2;  // mid는 현재 건널 수의 중간값

            // mid 횟수로 건널 수 있는지 확인하는 함수 호출
            if (isPossible(stones, k, mid)) {
                answer = mid + 1;  // 가능하다면, 더 큰 값을 시도해보기 위해 mid + 1로 설정
                left = mid + 1;  // 가능한 값을 더 크게 하기 위해 left를 mid + 1로 갱신
            } else {
                right = mid - 1;  // 불가능하다면, 가능한 값 범위를 좁히기 위해 right를 mid - 1로 갱신
            }

            // 디버깅용 출력 (이진 탐색의 진행상황을 확인)
            System.out.println("["+left+", "+right+"] = "+answer);
        }

        return answer;  // 최종적으로 건널 수 있는 최대 횟수를 반환
    }

    // 주어진 mid 값으로 stones 배열을 순회하며 k개 이상의 연속된 0이 있는지 확인하는 함수
    boolean isPossible(int[] stones, int k, int mid) {
        int cnt = 0;  // 연속된 0의 개수

        // stones 배열 순회
        for (int stone : stones) {
            // stone에서 mid를 뺀 값이 0 이하라면 해당 돌을 건널 수 없음
            if (stone - mid <= 0) {
                cnt += 1;  // 연속된 0의 개수를 증가시킴
                if (cnt >= k) {  // 연속된 0이 k개 이상이면 불가능하므로 false 반환
                    return false;
                }
            } else {
                cnt = 0;  // 연속된 0이 아니면 0으로 초기화
            }
        }
        return true;  // 연속된 0이 k개 미만이면 가능하므로 true 반환
    }
}

 

 

> python

 

def solution(stones, k):
    answer = 0
    
    left = 1;
    right = 200000000;
    
    while left <= right :
        mid = (int) (( left + right ) / 2)
        if isPossible(stones, k, mid) :
            answer = mid + 1
            left = mid + 1
        else :
            right = mid - 1
    
    return answer

def isPossible(stones, k, mid) :
    jump = 0
    for stone in stones :
        if stone - mid <= 0 :
            jump+=1
            if jump >= k :
                return False
        else :
            jump = 0
    return True