Algorithm

[Algorithm] 프로그래머스 - 징검다리

tenacy 2024. 7. 20. 13:42

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

접근

주어진 제한사항에서 rocks 배열의 길이가 50,000개 이하이므로 솔루션의 시간복잡도는 $O(N^2)$이 될 수 없다.

$O(N\log{N})$, $O(N\log{M})$이나 $O(N)$의 시간복잡도를 가지는 알고리즘을 선택해야 한다.

잘못된 초기 접근

펼치기/접기

나는 아쉽게도 $O(N)$의 시간복잡도로 문제를 해결하려고 시도했다. DP로 접근했다.

일단 주어진 rocks 배열을 오름차순으로 정렬시킨다. 근데, 이미 이 부분에서 $O(N\log{N})$이 됐다…

바위 사이의 거리를 담은 배열 d를 정의한다. 이 때, 시작지점과 도착지점도 포함하여 거리를 계산한다.

예를 들어, rocks 배열을 오름차순으로 정렬한 rocksAscending = [2, 11, 14, 17, 21]이 있다고 하자.

d 배열은 d = [2, 9, 3, 3, 4, 4]가 된다.

돌을 제거한다는 건 d 배열의 원소 사이의 장벽을 허문다는 뜻이다. 좀 이상할 수 있지만, 위 d 배열 표현에서 ‘,’를 없앤다고 생각하면 된다.

예를 들어, rocksAscending의 첫 번째 원소를 없앤다고 하자. 이에 따라 d 배열의 첫 번째 ‘,’를 없애면 d = [11, 3, 3, 4, 4]가 된다.

이 횟수가 총 n번이 될 때의 최솟값을 담은 배열에서 최댓값을 도출하려고 했다. 나는 이 횟수를 ‘합침’ 횟수라고 표현한다.

그래서 필요한 memoization 배열 dp를 다음과 같이 정의했다.

dp[m][0] - m에서 합치지 않을 때, m+1까지의 파생 배열에서의 최솟값

dp[m][1] - m에서 합칠 때, m+1까지의 파생 배열에서의 최솟값

dp의 자료형으로는 최솟값을 저장하는 정수형 멤버변수 min과, ‘합침’의 횟수를 저장하는 정수형 멤버변수 cnt를 구성하는 MinDistance 클래스이다.

문제 해결 접근은 d를 iteration 하면서 dp에 memoization을 수행한 후, 마지막으로 dp 원소 중 cnt가 n인 경우에 min 값의 최댓값을 찾겠다는 의도이다.

근데 여기서, 치명적인 오류가 있었다.

dp는 항상 최소가 되려는 방향으로 값을 저장하기 때문에 최종적으로 cnt가 n이 되지 않는 경우가 발생할 수 있다.

때문에, 나의 접근은 잘못됐다. 이 문제는 시간복잡도 $O(N)$의 성능을 내는 다이나믹 프로그래밍으로 풀 수 없다.

올바른 접근

$O(N\log{M})$의 시간복잡도를 가져도 충분히 이 문제를 해결할 수 있다.

이를 위한 알고리즘에는 이분 탐색 알고리즘이 있다.

이분 탐색 알고리즘은 다음 세 가지 절차에 의해 수행할 수 있다.

  1. 거리의 범위 설정
  2. 이분 탐색
  3. 결과 도출

1. 거리의 범위 설정

이 문제는 바위를 제거했을 때, 주어진 바위에서 최대로 점프할 수 있는 거리를 찾는 게 핵심이다.

여기서 최소로 점프할 수 있는 값이 시작 지점 left이고, 최대로 점프할 수 있는 값이 끝 지점 right이 된다.

즉, left=1, right=distance이다.

2. 이분 탐색

바위 사이 거리가 중간 거리 mid($=\frac{left+right}{2}$)보다 작으면 그 거리는 정답이 될 수 없으므로 해당 바위를 제거한다. 반대로, 크거나 같으면 제거하지 않는다.

mid 기준 바위를 제거했을 때 점프가 가능하다면 거리를 늘리고(left = mid + 1), 불가능하다면 거리를 줄인다(right = mid - 1).

3. 결과 도출

left와 right가 교차하여 넘어가면, 마지막으로 저장된 mid가 답이 된다.

소스코드(Java)

import java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);

        int left = 1;
        int right = distance;
        int result = 0;

        while (left <= right) {
            int mid = (left + right) / 2;
            int removedRocks = 0;
            int lastPosition = 0;

            for (int rock : rocks) {
                if (rock - lastPosition < mid) {
                    removedRocks++;
                } else {
                    lastPosition = rock;
                }
            }
            //마지막 바위 제거 처리
            if (distance - lastPosition < mid) {
                removedRocks++;
            }

            if (removedRocks <= n) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

 

이분 탐색($O(\log{M})$) 간에 rocks 배열을 iteration($O(N)$)하고 있으므로, 이 알고리즘의 시간복잡도는 $O(N\log{M})$이다.