백준 12738 : 가장 긴 증가하는 부분 수열 3

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

12738번: 가장 긴 증가하는 부분 수열 3

[ 문제풀이 ]

전형적인 LIS를 구하는 문제이다.

일반적으로 LIS는 DP로 구하지만 N이 최대 1,000,000이기 때문에 O(N^2)의 시간 복잡도로는 해결할 수 없다.

이는 세그먼트 트리나 LowerBound를 활용하면 O(NlogN)의 시간 복잡도로 해결할 수 있다. 나는 구현하기 더 간단한 LowerBound로 해결하였다.

다만, LowerBound를 활용하면 LIS의 길이는 구할 수 있지만 list에 존재하는 수들이 LIS가 아님을 주의해야 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			int N = Integer.parseInt(br.readLine());
			List<Integer> list = new ArrayList<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; ++i) {
				int data = Integer.parseInt(st.nextToken());
				if (i == 1 || list.get(list.size() - 1) < data) {
					list.add(data);
					continue;
				}
                
                  		//list에서 data보다 같거나 큰 수의 위치를 찾아서 변경
				int l = 0, r = list.size() - 1;
				while (l < r) {
					int m = (l + r) >> 1;
					if (list.get(m) >= data) r = m;
					else l = m + 1;
				}
				list.set(r, data);
			}
			bw.write(list.size() + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}