[Java] 백준 3745. 오름세

📌 문제 링크 - https://www.acmicpc.net/problem/3745

 

 

---

 

 

 

 

 

문제

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

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

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

 

 

 

---

 

 

풀이

LIS 문제이다.

 

LIS란 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)로, O(N log N)의 시간 복잡도를 가진다.

주어진 수열에서 일부 원소를 제거하여 얻을 수 있는 증가하는 부분 수열 중 가장 긴 것을 의미한다. 

 

예를 들어 [10, 20, 10, 30, 20, 50]의 LIS는 [10, 20, 30, 50]이 된다.

 

LIS를 구하는 과정은 다음과 같다.

1. 배열을 순회하면서 LIS를 유지할 배열 lis를 만든다. 
2. arr[i]를 lis 배열의 적절한 위치에 삽입해 준다.
   • arr[i]가 lis의 마지막 원소보다 크다면 lis의 끝에 추가해 준다.
   • arr[i]가 lis의 마지막 원소보다 크지 않다면 lis에 들어갈 수 있는 적절한 위치를 이분 탐색을 통해 찾아서 교체해 준다. (길이는 유지)
3. 최종적으로 lis 배열의 길이가 LIS의 길이가 된다.

 

 

이 문제에서 변수명은 arr은 P로, lis는 dp로 사용하였다.

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/3745
public class Main_3745 {
    private static int N;
    private static int[] P; // N일 동안의 주가


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder ans = new StringBuilder();
        StringTokenizer st;
        String input;

        while((input = br.readLine()) != null) {
            input = input.trim();
            if(input.isEmpty()) break;

            N = Integer.parseInt(input.trim());
            P = new int[N];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++) {
                P[i] = Integer.parseInt(st.nextToken());
            }

            int length = getMaxLength();
            ans.append(length).append('\n');
        }

        System.out.print(ans);
    }//main


    private static int getMaxLength() {
        int cnt = 0;
        int idx = 0;
        int[] dp = new int[N+1];

        for(int i=0; i<N; i++) {
            if(P[i] > dp[cnt]) {
                dp[++cnt] = P[i];
                continue;
            }

            idx = getIndex(cnt, P[i], dp);
            dp[idx] = P[i];
        }

        return cnt;
    }//getMaxLength


    private static int getIndex(int end, int target, int[] dp) {
        int start = 0;
        int mid;

        while(start < end) {
            mid = (start + end) / 2;

            if(dp[mid] < target) start = mid + 1;
            else end = mid;
        }

        return end;
    }//getIndex


}//class