백준 12015 - 가장 긴 증가하는 부분 수열 2

문제

https://www.acmicpc.net/problem/12015

풀이

LIS 문제인데, 주어지는 배열의 길이($N$)가 최대 $1,000,000$이므로 $O(NlogN)$
이내에 풀이해야 한다.

이진 탐색을 활용하면 해당 복잡도 내에 문제를 풀이할 수 있다. Collections.sort는 다음과 같이 동작한다.

• 컬렉션에 요소가 존재하면 해당 요소의 인덱스를 반환
• 컬렉션에 요소가 존재하지 않으면 -(해당 요소가 들어갈 위치 + 1) 값 반환
  • [10, 20, 30]에서 25를 탐색할 경우 들어갈 위치는 20과 30 사이
  • 20의 뒤 위치인 2에 1을 더한 후 음수값을 취하여 -3을 반환

컬렉션에 요소가 존재하지 않을 때 값을 역으로 변환하여 한 요소의 LIS 배열 내 위치를 구할 수 있다. LIS 길이 정보를 제공할 리스트를 정의하고, 주어진 배열의 원소를 순회하며 LIS 리스트에 들어갈 위치를 계산한다. 들어갈 위치가 현재까지의 리스트 길이와 같다면 리스트에 추가하며 LIS 길이를 연장하고, 그 외에는 들어갈 위치의 값을 갱신해준다.

배열의 순회하며 이진탐색을 수행하는 시간복잡도가 $O(NlogN)$이므로 최악의 경우에도 제한 조건 1초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        int[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        List<Integer> lis = new ArrayList<>();
        for (int num : arr) {
            int index = Collections.binarySearch(lis, num);
            if (index < 0) index = -(index + 1);

            if (index == lis.size()) {
                lis.add(num);
            } else {
                lis.set(index, num);
            }
        }

        System.out.println(lis.size());
        br.close();
    }
}

결과