[백준] 12015 가장 긴 증가하는 부분 수열2 - Java

 

문제 출저

https://www.acmicpc.net/problem/12015

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

 

 

문제 풀이 

가장 긴 증가하는 부분 수열을 구해야 한다.

다만 n이 커서 for문 돌리기에는 시간 초과가 발생합니다.

 

시간 단축을 위해 이분 탐색을 도입해야 합니다. 

이 문제는 부분 수열의 길이를 구하는 것으로 내용물은 몰라도 되는게 핵심입니다. 

 

int[] board 배열을 만들어 주어진 배열을 담았습니다. 

List<Integer> list를 생성하여 부분 수열을 만들었습니다. 이 때 처음에 0을 넣는다.

board를 탐색하면서 list를 만듭니다.

이 때, list의 가장 최근에 들어온 값과 board[i]를 비교하여 board[i]가 크면 list에 추가합니다.

만약 작다면 대체해야할 자리값을 찾는다. 이 때 이분탐색을 진행한다. 

처음에 0을 넣었으니 정답에 list의 크기에 -1을 해서 정답을 출력한다.

 

 

소스 코드

package baekjoon.backjoon9.day13;


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

/*
가장 긴 증가하는 부분 수열2
https://www.acmicpc.net/problem/12015
 */
public class B12015 {

    static int n;
    static int[] board;
    static List<Integer> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }

        list = new ArrayList<>();
        list.add(0);

        for(int i = 0; i < n; i++) {
            if(list.get(list.size()-1) < board[i]) {
                list.add(board[i]);
            }
            else {
                int index = find(board[i]);
                list.set(index, board[i]);
            }
        }



        StringBuilder sb = new StringBuilder();
        sb.append(list.size()-1);
        System.out.println(sb);

    }

    public static Integer find(int number) {

        int start = 0;
        int end = list.size()-1;

        int result = 0;

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

            if(list.get(mid) < number) {
                start = mid + 1;
                result = start;
            }
            else {
                end = mid;
            }
        }

        return result;

    }
}