백준 1365 자바 - 꼬인 전깃줄 (BOJ 1365 JAVA)

문제 : boj1365

 

 

  이 단어를 제가 쓰게될줄은 몰랐는데.. 'Well-Known'한 문제이다. DP쪽엔 냅색류가 유명하듯, 이분탐색쪽도 뭔가 선 꼬인거에서 안꼬이게 최대치 이런 종류의 문제가 유명하다. 사실 이런 류의 문제를 접해보지 못했다면 아이디어를 떠올리기 힘들 수 있다.

 

  아이디어는 어떨 때 꼬이는지를 확인해보면 된다. -> 간단히 순서대로 선을 이어줄 때, 직전에 들어왔던 입력값보다 작은 값이 입력되면 꼬이게 된다. 예를들어 아래와 같은 경우 좌측의 순서대로 우측에 매칭된 숫자는 1, 3, 4, 2가 된다. 이 때 꼬인 부분은 이전보다 작은 값이 들어온 [4, 2] 부분이 된다.

  

  그럼여러 경우를 테스트 해보면, 위와 같이 서로 겹치지 않게(안꼬이게) 하려면 단순히 subsequence(1,3,4,2의 subsequence는 [1], [3], ..., [1,3], [1.4], [1,2], ..., [1,3,4], [1,3,2],... 등) 중 증가하는 순서로 가장 긴 길이를 찾으면 된다는걸 알 수 있다. 이 문제의 경우엔 가장 긴 길이를 찾아서 전체 길이에서 빼면 그게 제거해야하는 최소 개수가 된다.

 

  이렇게 가장 길이가 긴 증가하는 subsequence를 찾는 알고리즘을 LIS (Longest Increasing Subsequence) 알고리즘이라고 한다. 알고리즘 자체에 대한 설명은 나중에 따로 적어두겠다. LIS 구현은 뭐 Brute Force로도 O(N^2)으로 가능한데, 이 문제와 같이 N이 100000정도부터는 당연히 O(N^2)으로 불가하다. 이분탐색(Binary Search)을 사용하면 O(NlogN)으로 LIS 구현이 가능하다. 내 경우엔 Binary Search Tree로 구현되어 있는 TreeSet을 사용하여 LIS를 구현해봤다(물론 이분탐색을 직접 짜도 되겠지만, 자바에도 Collections 클래스에 binarySearch 함수가 있어서 List에 데이터를 담아서 자바에서 제공하는 binarySearch 사용이 가능하다. 또는 내 경우처럼 TreeSet으로 구현해도 상관없다. 사실 TreeSet이 c++에서 자주 사용되는 lower_bound, upper_bound도 구현되어 있어서 더 사용하기 편하다.).

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.TreeSet;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(0);
        for (int i = 0; i < n; i++) {
            int cur = nextInt();
            if (ts.last() > cur) {
                ts.remove(ts.ceiling(cur));
            }
            ts.add(cur);
        }
        System.out.println(n - (ts.size()-1));
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}