[백준]#3745 오름세

문제

주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.

정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다.

n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다.

n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. 주가는 한 개 이상의 공백으로 구분되어 있으며, 그 외의 위치에서도 자유롭게 나올 수 있다. 주가는 100,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 주가의 가장 긴 오름세의 길이를 출력한다.

예제 입력 1

6
5 2 1 4 5 3
3
1 1 1
4
4 3 2 1

예제 출력 1

3
1
1

풀이

이 문제는 LIS(가장 긴 증가하는 부분수열) 알고리즘을 이용해서 풀어야 하는 문제이다. 이전의 LIS 문제들은 dp를 이용해서 풀었으나 dp를 이용하면 O(n^2) 이기 때문에 시간초과가 생긴다. 그래서 O(nlogn)으로 풀 수 있는 알고리즘을 사용했다. arraylist는 값 교체에 시간이 오래걸려서 배열로 바꿔서 다시 풀었다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()) {
            int N = sc.nextInt();
            int[] lis = new int[N];
            int[] arr = new int[N];
            for(int i=0; i<N; i++)
                arr[i] = sc.nextInt();

            int idx = 0;
            for(int temp : arr) {
                if (idx==0 || temp>lis[idx-1]) {
                    lis[idx] = temp;
                    idx++;
                }

                else {
                    int i = 0;
                    int j = idx - 1;

                    while (i<j) {
                        int mid = (i+j)/2;

                        if(lis[mid]<temp)
                            i = mid+1;

                        else
                            j = mid;
                    }

                    lis[j] = temp;
                }
            }

            System.out.println(idx);
        }
    }
}