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

프로그래머스 64062번

 

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

프로그래머스

 

효율성 부분이 있어서 입력값 개수를 봤더니 

stones 배열의 크기가 최대 200,000개이고 각 원소들의 값이 최대 200,000,000이다.

 

각 stones에 200,000,000씩 들어가 있고 니니즈 친구들의 수는 2억명까지도 될 수 있기 때문에

그냥 배열 돌리기를 해버리면 입력값이 너무 커서 시간 초과가 뜨게 된다.

 

아래 코드는 그냥 배열 돌리기한 코드이다.

 

정확성 100% 코드 & 효율성 0% 코드

import java.util.*;

class Solution {
    static int MAX = 0, N, K;
    static int[] stones;
    public int solution(int[] s, int k) {
        int answer = 0;
        N = s.length;
        K = k;
        stones = s;
        while(true) {
            boolean result = steppingStone();
            if (!result) {
                break;
            }
        }
        answer = MAX;
        return answer;
    }
    
    public static boolean steppingStone() {
        int t = 0;
        for(int i = 0; i < N; i++) {
            if (stones[i] == 0) {
                t += 1;
                if (t == K) {
                    return false;
                }
                continue;
            }
            stones[i] -= 1;
            t = 0;
        }
        MAX += 1;
        return true;
    }
}

결과는 보나마나..

효율성 35.9를 위해 대대적인 코드 수리에 들어간다.

 

코드 수리를 위한 생각 확장

이 문제를 풀기 위해서는 이분탐색을 사용해야 한다.

 

이분탐색은 최적화 문제에 많이 사용되는데, 최적화 문제란 어떤 조건(condition(x))을 만족하는 x의 최댓값, 최소값을 찾는 문제를 말한다.

이때, condition(x)에 대해 x가 이분적이면 이분탐색을 적용할 수 있다고 한다.

 

백준에서 정리해놓은 이분 탐색 구현을 보며 이분 탐색을 공부했다.

 

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

이분 탐색을 구현하는 세 줄 요약이다.

위의 방법을 적용해서 징검다리 건너기를 생각해보자.

 

일단, 문제에서 이분적인 성격을 지닌 요소를 찾아보면 니니즈 친구들이다.

니니즈 친구들은 건널 수 있거나 없거나 두 가지 특징을 가진다.

 

따라서, 니니즈 친구들을 x로 하고 조건은 징검다리를 건널 수 있느냐 없으냐 이다.

 

결정 문제의 답이 이분적일 때 사용할 수 잇는 탐색 기법이기 때문에 이분 탐색을 사용해서 결정 문제의 답이 달라지게 된다.

 

그래서, 징검다리 건너기에서 최대로 건널 수 있는 니니즈 친구를 구할 때, 다리를 건널 수 있는가? 라는 결정 문제에서 최대로 건널 수 있는 니니즈 친구 수가 x라고 한다면 x 이후에는 건널 수 없음으로 x는 징검다리 건너기 문제의 답이 달라지는 경계라고 볼 수 있다.

 

lo는 0이고, hi는 200,000,000이다.

위의 Check에 해당하는 코드는 징검다리를 건널 수 있는가 없는가로 나타내면 될 것 같다.

 

hi는 징검다리에 적혀진 숫자 중 제일 큰 숫자를 나타내면 되는데, 200,000,000으로 그냥 설정해도 되고 최대 200,000인 stone을 하나씩 둘러보면서 제일 큰 수를 찾아도 된다.

 

그렇다면 조건(Check)만 정하면 되는데, 0이 적힌 돌이 k개 있으면 니니즈 친구들은 건널 수 없다. 돌에 적힌 숫자는 해당 돌다리를 건너면 1씩 줄어든다.

그렇기 때문에 징검다리를 건너려고 하는 니니즈 친구들 숫자보다 돌에 적힌 숫자가 적은 경우가 k번 연속으로 발생할 경우 조건이 실패한다고 보면 된다.

정확성 100%에 효율성 100%를 곁들인 코드

import java.util.*;

class Solution {
    static int K;
    static int[] stones;
    public int solution(int[] s, int k) {
        int answer = 0;
        K = k;
        stones = s;
        int lo = 0, hi = 200000000, mid;
        
        while(lo <= hi) {
            mid = (lo + hi) / 2;
            
            if (check(mid)) {
                lo = mid + 1;
                if (answer < mid) {
                    answer = mid;
                }
            } else {
                hi = mid - 1;
            }
        }
        return answer;
    }
    // 인원 수보다 돌에 적혀진 숫자가 작은 경우가 k번 연속으로 발생할 경우 false
    public static boolean check(int mid) {
        int t = 0;
        for(int i = 0, size = stones.length; i < size; i++) {
            if (stones[i] < mid) {
                t += 1;
                if (t == K) {
                    return false;
                }
                continue;
            }
            t = 0;
        }
        return true;
    }
    
}

 

느낀 점

효율성을 따지는 문제가 반드시 출제되기 때문에 이것을 풀이하는 방법을 많이 알아두면 좋을 것 같다는 생각이 들었다.

입력값이 커지면 커질수록 필요한 부분과 필요하지 않은 부분을 나눌 필요가 있다는 생각이 들었다.

그런 의미에서 이분 탐색이 큰 입력값에 대응하기에 적절한 알고리즘이라는 생각이 들었다.