[BOJ 백준] 가장 긴 증가하는 수열5 (14003) Java

링크 : https://www.acmicpc.net/problem/14003

 

문제 설명 : 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력 :

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

출력 : 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

예제 입력 : 

6

10 20 10 30 20 50

 

예제 출력 : 

4

10 20 30 50

 

 

접근법 : 

1) 어떻게 풀 것인가?

N이 100만으로 큰 편이다. N log N 로직이 아니면 통과가 힘들다.

 

가장 긴 증가하는 부분 수열은 LIS (LIS, Longest Increasing Subsequence)로 많이 알려진 알고리즘인데,

N log N으로 해결하는 방법으로는 이진탐색을 활용하는 방법이 있다.

 

이진탐색은 lower_bound 라이브러리를 사용해도 된다.

직접 구현한다면 함수는 아래와 같다.

	static void binarySearch(int id) {
		int start, end, mid;
		start = 0;
		end = LIS.size() - 1;

		while (start < end) {
			mid = (start + end) / 2;
			// 값이 더 크면 - lower bound 로직
			if (LIS.get(mid) >= input[id]) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		// LIS 배열 갱신해주고, 위치 기록
		LIS.set(start, input[id]);
		index[id] = start;
	}

 

전체 코드는 아래 참고.

 

2) 시간복잡도

O(NlogN)이지만 수열 크기가 100만개가 될 수 있으므로, 출력에 주의해야함. (StringBuilder insert 사용 X)

(Java 기준 -  1,056ms)

 

3) 공간복잡도

1차원 배열로 충분하므로 고려하지 않음

 

4) 풀면서 놓쳤던점

정답을 출력할때 StringBuilder sb.insert(0, "값"); 을 하는 방식으로 했더니 시간초과가 발생했다.

sb.append("값")으로 바꾸니 약 1,000ms에 통과했다.

아마도, StringBuilder가 커질 경우 insert를 할때 많은 시간을 소요하는것 같다.

 

5) 이 문제를 통해 얻어갈 것

분할정복 코드 작성법

 

Java 코드 : 

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

// 14003 가장 긴 증가하는 부분 수열 5 
public class Main {

	static int N;
	static int[] input, index; // index[i] : input[i]가 LIS에 들어간 위치
	static ArrayList<Integer> LIS;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// 1. 입력받기
		N = Integer.parseInt(br.readLine());
		input = new int[N + 1];
		index = new int[N + 1];
		LIS = new ArrayList<Integer>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		// ** N은 1이면 바로 끝내기
		if (N==1) {
			System.out.println("1\n"+input[0]);
			br.close();
			return;
		}
		
		LIS.add(input[0]);
		index[0] = 0;
		// 2. 이진탐색을 활용한 LIS 배열 만들기
		for (int i = 1; i < N; i++) {
			// 1) 값이 더 클 경우 LIS 리스트에 새로 추가
			if ( input[i] > LIS.get(LIS.size() - 1)) {
				LIS.add(input[i]);
				index[i] = LIS.size() - 1;
			} 
			// 2) 값이 작은 경우 LIS 리스트 중 이진탐색으로 lowerbound에 추가
			else {
				binarySearch(i);
			}
		}

		// 3. 정답 출력
        sb.append(LIS.size() + "\n");
        // 역추적 경로를 저장할 stack
        Stack<Integer> stack = new Stack();
        int findCnt = LIS.size() - 1;
        for(int i = N-1; findCnt>=0 && i >= 0; i--){
            if(index[i] == findCnt){
            	findCnt--;
                stack.push(input[i]);
            }
        }
        while (!stack.isEmpty()){
            sb.append(stack.pop() + " ");
        }
        System.out.println(sb.toString());
        
		br.close();
	}

	static void binarySearch(int id) {
		int start, end, mid;
		start = 0;
		end = LIS.size() - 1;

		while (start < end) {
			mid = (start + end) / 2;
			// 값이 더 크면 - lower bound 로직
			if (LIS.get(mid) >= input[id]) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		// LIS 배열 갱신해주고, 위치 기록
		LIS.set(start, input[id]);
		index[id] = start;
	}
}