(프로그래머스) 징검다리 건너기

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

 

🐢 설명

• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.

니니지의 친구들이 길이가 최대 20만인 돌다리를 건너야하고, 해당 돌다리의 내구성은 최대 2억이다.

 

한명씩 건너게 하고 내구도를 1씩 낮추고 배열을 탐색하면서 0의 개수를 세서 한번에 건널수 있는 최대인 k와 비교할 경우 시간복잡도는 20만개의 돌다리가 전부 2억의 내구도를 가지는 경우 O(20만 * 2억)를 갖게된다. 감히 생각도 할 수 없을 만큼 큰 연산을 해야하므로 이렇게 풀어서는 안된다.

 

Q. 그렇다면 어떻게 접근해야 딱 k개 이상의 돌이 무너져서 건널 수 없는지 알 수 있을까?

A. 이분탐색을 이용하면 된다. 중간값을 찾아서 내구도를 줄여보고 건널 수 있는지 없는지 판단한다.

 

로직

1. 건너야 하는 돌들의 내구성을 기준으로 먼저 정렬을 한다.
2. 정렬된 돌들 중 mid 돌을 뽑고 해당 돌의 무게(w)를 기존의 돌다리에서 빼보면서 0보다 작거나 같은 경우 카운트를 증가시킨다.
   • 이 경우가 한번에 건너야 하는 거리를 세는 부분이다.
   • 만약, w보다 크다면 건넌 것이므로 카운트를 0으로 초기화한다.
3. 카운트를 증가시키다가 k(최대 건널 수 있는 크기)가 되면 못건넌다는 것을 의미하므로 해당 돌의 무게를 일단 저장하고, 다시 mid를 잡고 탐색한다.
   • 돌의 무게가 이미 건넌 친구들의 횟수를 의미하므로 건너지 못한 돌의 무게를 반환하면 되는 것이다.

 

돌의 개수가 20만개가 있어도 원하는 내구도를 찾기 위해서는 최대 19번의 탐색만 있으면 된다. 2^19 >= 20만이므로. 따라서 내구도를 찾는데 19 * 돌다리의 길이 20만으로 줄어들게 되어 약 400만으로 O(N)이 된다.

 

문제 예제에 적용해보자

2 4 5 3 2 1 4 2 5 1 (돌다리)

1 1 2 2 2 3 4 4 5 5 (정렬된 돌다리 내구성)

left = 0; right = 10;

 

mid = 5;
w = 3;
0 1 2 0 0 0 1 0 2 0 (못건넌다)

right = mid(5)

mid =  2;

w = 2;
0 2 3 1 0 0 2 0 3 0 (건넌다)

left = mid(2) + 1;

mid = 4;

w = 2;
0 2 3 1 0 0 2 0 3 0 (건넌다)

left = mid(4) + 1;

 

left < right 조건으로 인해 반복문 종료. answer는 w(3)이 된다.

 

🐢코드

import java.util.*;

class Solution {
    static int[] sortStones;
    
    public int solution(int[] stones, int k) {
        sortStones = stones.clone();
        
        Arrays.sort(sortStones);
        
        int answer = binarySearch(stones, k);
        
        return answer;
    }
    
    private static int binarySearch(int[] stones, int k)
    {   
        int left = 0;
        int right = stones.length;
        int mid;
        int w = 0;
        int answer = 0;
        
        while (left < right)
        {
            mid = (left + right) / 2;
            w = sortStones[mid];
            
            if (go(stones, w, k)) {
                left = mid + 1;
            } else {
                right = mid;
                answer = w;
            }
        }
        return answer;
    }
    
    private static boolean go(int[] stones, int w, int k)
    {
        int zeroCnt = 0;
        
        for (int i = 0; i < stones.length; i++) {
            if (stones[i] <= w) zeroCnt++;
            else zeroCnt = 0;
            
            if (zeroCnt == k) return false;
        }
        return true;
    }
}

 

🐢 마무리