[BOJ] 백준 3745번 오름세 (Java)

#3745 오름세

난이도 : 골드 2

유형 : LIS / DP / 이분 탐색

3745번: 오름세

▸ 문제

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

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

가장 긴 증가하는 부분 수열 LIS 문제이다. LIS는 DP라는 배열에 따로 증가하는 부분 수열을 저장하여 해당 길이를 출력하는 방법인데, DP에 넣을 값을 갱신할 때 선형 탐색이 아닌 이분 탐색을 이용하여 인덱스 위치를 찾기 때문에 이분 탐색이 필요하다.

• 따라서 이분 탐색을 이용하면 O(n^2)으로 처리해야 할 로직은 O(n*logn)으로 처리할 수 있다.

LIS에 대한 자세한 내용은 여기를 참고해주세요

 

먼저 n일 동안의 주가를 담은 arr배열을 선형 탐색을 한다. 그리고 각 값을 DP배열에서 가장 큰 값과 비교하여 증가하는 부분 수열을 만들어주면 된다.

• if(arr[i] > dp[len]), dp에서 가장 큰 값보다 arr[i]가 더 크므로 LIS에 넣어준다.
• else, 현재 arr[i]는 LIS 중간에 위치하므로 lower_bound를 이용하여 삽입할 인덱스 위치를 구해준다.
  
  • lower_bound는 dp 배열 중 현재 arr[i]보다 크거나 같은 첫번째 인덱스를 리턴한다.

int len = 0;
int idx = 0;
for (int i = 0; i < n; i++) {
	if(arr[i] > dp[len]) {
		dp[++len] = arr[i];
	}else {
		idx = lowerbound(0, len, arr[i]);
		dp[idx] = arr[i];
	}
}

 

[5 6 7 1 2 3 4]에 대한 배열을 LIS를 구하는 시뮬레이션을 돌리면 다음과 같다.

• arr[0] = 5 > dp[len=0] 이므로, LIS배열에 삽입해주고 len++
• arr[1] = 6 > dp[1] = 5 이므로,  LIS배열에 삽입해주고 len++
• arr[2] = 7 > dp[2] = 6 이므로,  LIS배열에 삽입해주고 len++
• arr[3] = 1 <= dp[2] = 6 이므로, LIS 배열에 위치할 인덱스를 구해준다.
  • lower_bound = 0 이므로, dp[0] = 1 을 갱신한다.

 

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static int[] arr, dp;
	public static void main(String[] args){
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));){
			String line = null;
			while((line = br.readLine()) != null) {
				int n = Integer.parseInt(line.trim());
				arr = new int[n];
				dp = new int[n+1];
				
				st = new StringTokenizer(br.readLine());
				for (int i = 0; i < n; i++) {
					arr[i] = Integer.parseInt(st.nextToken());
				}
			
				int len = 0;
				int idx = 0;
				for (int i = 0; i < n; i++) {
					if(arr[i] > dp[len]) {
						dp[++len] = arr[i];
					}else {
						idx = lowerbound(0, len, arr[i]);
						dp[idx] = arr[i];
					}
				}
				sb.append(len+"\n");
			}
			
		} catch(Exception e ) {
			
		} finally {
			System.out.println(sb.toString());
		}
		
	}
	
	static int lowerbound(int s, int e, int key) {
		while(s < e) {
			int mid = (s+e)/2;
			
			if(dp[mid] >= key) {
				e = mid;
			}else {
				s = mid+1;
			}
		}
		return e;
	}
}