[BAEKJOON] 12015 가장 긴 증가하는 부분 수열 2

문제 요약

• 알고리즘 분류: 이분탐색
• 난이도: Gold2
• 문제내용:
  • 수열 A가 주면 가장 긴 증가하는 수열의 길이를 구해라

• 사이트: https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

문제풀이

 이번 문제는 LIS문제인데 1,000,000크기 데이터로는 DP로 풀기에는 시간 초과가 난다. 그래서 이분 탐색으로 풀어야 된다. 그 부분은 아래의 사이트에서 확인 해보면 된다. 아래 사이트에 이분 탐색으로 구현한 코드있으면 거기 코드 보고 약간 추가만 해주면 통과가 될거이라고 생각한다.

https://jih3508.tistory.com/46

[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

Code

Python

 이번에는 bisect 함수로 간단하게 처리 했다.

import bisect
N = int(input())
array = list(map(int, input().split()))

#처음에 맨 뒤에 값이랑 비교하기위해서 수열 부분에 첫번째 인덱스 값이 옴
sequense = [array[0]]
for num in array[1:]:
    if sequense[-1] < num:
        sequense.append(num)
    else:
        sequense[bisect.bisect_left(sequense, num)] = num

print(len(sequense))

Java

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] array = new int[N];
		int[] sequense = new int[N];
		
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		// 처음에 맨 뒤에 값이랑 비교하기위해서 수열 부분에 첫번째 인덱스 값이 옴
		sequense[0] = array[0];
		int start, end, mid;
		int size = 0; // sequense의 현재 배열 사이즈
		for(int i = 1; i < N; i++) {
			if (sequense[size] < array[i]) {
				size++;
				sequense[size] = array[i];
			}else {
				start = 0;
				end = size;
				while(start <= end) {
					mid = (start + end) / 2;
					if (sequense[mid] >= array[i]) {
						end = mid - 1;
					}else {
						start = mid + 1;
					}
				}				
				sequense[start] = array[i];
			}
		}
		
		System.out.println(size + 1);	
	}
		
}