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

문제출처

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

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

 

문제풀이

문제를 풀기 이전에 이분탐색에 대해 익숙하지 않다면 이글을 먼저 읽는게 이해가 빠르실 겁니다.

[Algorithm] - [프로그래머스 43238] - 입국심사

[프로그래머스 43238] - 입국심사

입국심사 문제와 같이 이분탐색을 이용한 문제입니다. 

한번에 건너뛸 수 있는 칸수 = k
stones = 징검다리 값

lowCount = 최소 인원수

highCount = 최대 인원수

averageCount = 건널 수 있는 인원수

 

문제의 핵심은 이분탐색 문제로 재해석 하는 것이다. 건넌 사람이 3명인경우 stone[i] - 3의 값이 양수여야 다리가 남아있는 경우이다. 이외의 경우 징검다리가 사라진 경우여서 건너뛰어야 하며 건너뛰는 징검다리 수를 저장하는 jumpCount변수에 저장한다.

jumpCount 변수는 최대 점프 횟수인 k를 넘을 수 없으며 k이상인 경우 최대 건너뛸 수 있는 사람의 제한을 줄여 재 탐색한다.

 

n = 건넌 사람

stones[i] = 징검다리 값

 

 

문제를 푸는데 입국심사 문제가 큰 도움이 되었다. 이해가 잘 되지 않는다면 위에있는 입국심사 포스팅을 읽고 문제를 풀어보면 더 쉬울거라 생각된다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0.java

sw93/algorithm

class Solution {
   
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        // 건너뛰는 최소 인원수
        int lowCount = 1;   
        
        // 건너뛰는 최대 인원수
        int highCount = Integer.MAX_VALUE;  
        
        // 이분탐색에서 이용할 중간값
        int averageCount = (lowCount + highCount) / 2;  
        
        while (lowCount <= highCount) {
            averageCount = (lowCount + highCount) / 2;
            
            // 건너뛴 징검다리 수
            int jumpCount = 0;
            for (int i=0; i<stones.length; i++) {
                if (stones[i] - averageCount <= 0) {
                    jumpCount++;
                } else {
                    jumpCount = 0;
                }
                
                // k개 이상 건너뛰어야 하는경우 건너뛰는 인원수를 반으로 줄인다
                if (jumpCount >= k) {    
                    highCount = averageCount - 1;
                    break;
                }
            }
            
            // 건너뛴 징검다리 개수가 k개 미만인 경우 인원수를 늘린다.
            if (jumpCount < k) {
                lowCount = averageCount + 1;
                answer = lowCount;
            }  
        }

        return answer;
    }
}