[BOJ] 1365. 꼬인 전깃줄 (🥇, 이분 탐색)

🔗

풀이

최장 증가 부분 수열 문제이다.

나열된 전봇대의 숫자들 중에 가장 긴 증가하는 연속된 수열을 찾으면 된다. 1부터 N번까지 탐색하면서 매번 현재의 값보다 큰 값 중 가장 최소인 값을 찾아 그 값을 대체하는 방식을 택하게 된다.

위와 같은 수열이 있을 때 노란 수열은 길이3이고 빨간 수열은 길이5로 후자가 최장 증가 부분 수열이 된다. 앞에서부터 탐색을 진행하게 되면 2 5 7 까지만 탐색해서 길이3의 수열을 찾게 되는데 그 다음 숫자인 3이 오게 되면 여기서부터는 이어지는 최장 수열이 아니기 때문에 2 5 7 중에서 3과 이어져서 최장 증가 부분 수열을 이룰 수 있는 부분이 어디부터인지 찾아야 한다. 쉽게 말해 3보다 작은 숫자를 찾아야 한다. 이 값부터 3이 다시 최장 증가 수열을 이룰 수 있기 때문이다.

이 수를 찾는 방법은 쉽게 생각해서 완전 탐색을 돌리면 될 것 같지만 N의 최대 크기가 10만이기 때문에 최악의 경우 시간 복잡도가 O(N^2)가 될 수 있다. 이 수열이 정렬 되어 있다는 점을 고려하면 이분 탐색을 사용해서 찾을 수 있다. 이분 탐색의 시간 복잡도는 O(logN)이기 때문에 최대 약 13번의 탐색으로 해당 값을 찾을 수 있게 된다. 아무리 오래 걸려도 탐색 횟수 130만이면 탐색을 완료할 수 있다.

이때 찾아야 하는 값은 해당 값(3)보다 큰 값들 가운데 최소가 되는 값이다. 더 작은 값을 찾아야 하지 않냐고 생각할 수 있는데 만약 1 3 3 3 4 와 같이 된 경우 3을 더 작은 값의 위치인 1에 연결하게 되면 전깃줄이 꼬이게 된다. 그래서 3보다 크면서 최소인 값인 4를 찾아서 그 값을 3으로 교체해야 한다. 그래도 이어지는 최장 증가 부분 수열이 될 수 있다. 하지만 해당 문제는 조건 상 2대 이상과 연결된 전봇대는 없다고 했으므로 같은 값이 존재하지 않을 것이므로 그냥 최소 값을 찾아도 상관없다.

3 이전의 값들은 이미 2 5 7 의 수열을 이루고 있는데 이때 3보다 큰 값 중 최소값이 되는 5를 3으로 대체한다. 그렇게 되면 2 3 7이 되어서 분명 이어지는 부분 수열은 아니게 되는데 결국 문제에서 원하는 것은 길이지 부분 수열을 이루는 숫자들이 아니기 때문에 이렇게 대체한다고 해도 문제될 것은 없다. 만약 3 이후의 숫자가 없다면 2 5 7 이 최장 부분 증가 수열이 되며 이때 해당하는 길이 3을 출력하면 되고, 3 이후의 숫자가 3에 이어서 최장 증가 부분 수열이 될 수 있다면 3을 교체한 방식과 마찬가지로 교체해서 새로운 최장 증가 부분 수열을 만들어내면 되는 것이기 때문이다. 결국 이렇게 더 작은 값들로 숫자를 교체하는 이유는 뒤이어 나오게 될 숫자들을 가지고 최장 증가 부분 수열을 만드는데 유리할 것이기 때문이다. 5를 3으로 교체하면 뒤에 나오는 숫자 4 5 7 을 가지고 더 긴 길이의 수열을 만들 수 있다. 만약 5를 그대로 내버려 둔다면 3 4를 포기해야 할 것이다.

최종적으로 수열은 2 3 4 6 7 로 길이 5의 최장 증가 부분 수열을 가질 수 있게 된다.

import java.util.*;
import java.io.*;

public class Main {
    static int binarySearch(int x, int[] arr, int rightIdx) {
        int leftIdx = 0;
        int midIdx;
        while (leftIdx <= rightIdx) {
            midIdx = (leftIdx + rightIdx) / 2;

            if (arr[midIdx] < x) {
                leftIdx = midIdx + 1;
            } else {
                rightIdx = midIdx - 1;
            }
        }
        
        arr[leftIdx] = x;
        return leftIdx;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] telephonePole = new int[N];
        Arrays.fill(telephonePole, Integer.MAX_VALUE);

        telephonePole[0] = sc.nextInt();
        int maxLength = 0;
        for (int i = 0; i < N-1; i++) {
            int inputNumber = sc.nextInt();
            int idx = binarySearch(inputNumber, telephonePole, maxLength);
            maxLength = Math.max(idx, maxLength);
        }

        System.out.println(N - maxLength - 1);
    }
}