백준 12015 자바 - 가장 긴 증가하는 부분 수열 2 문제

www.acmicpc.net/problem/12015

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

 

가장 긴 부분 수열의 길이를 구하는 문제로 

전체 리스트를 한번만 돌아서

임으로 만든 listFroSize 배열을 변경해나면서 사이즈를 구함.

 

1. listFroSize에 0을 추가

2. 입력받는 arr를 순회

- 1) arr의 인자 값이 listFroSize의 마지막 값보다 큰 경우 추가

- 2) arr의 인자 값이 listFroSize의 마지막 값보다 작은 경우 이진 탐색

     - 이진탐색을 통해서 right 값을 arr의 인자값으로 수정

3. listForSize -1 값 출력(임으로 추가했던 0을 제외하기 위해서)

 

입력이 아래의 경우 

6 
10 20 10 30 20 50

 

(인자값 -> listForSize 배열)

0과 10 비교 -> 10추가

10 -> 0 10

10과 20 비교 -> 20추가

20 -> 0 10 20

20과 10 비교 -> 이진탐색

10 -> 0 10 20

20과 20 비교 -> 이진탐색

20 -> 0 10 20

20과 50 비교 -> 50추가

50 -> 0 10 20 50

 

위의 경우로 잘 이해가 안되서 다른 예를 들어보았습니다.

4
10 20 30 28

0과 10 비교 -> 10추가

10 -> 0 10

10과 20 비교 -> 20추가

20 -> 0 10 20

20과 30 비교 -> 30추가

30 -> 0 10 20 30

30과 28 비교 -> 이진탐색

20 -> 0 10 20 28

위처럼 마지막보다는 작고 마지막 바로 이전것 보다 크면 마지막 값이 변경됩니다.

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

// 가장 긴 증가하는 부분 수열 2 문제 - 12015번
public class LIS2 {

    static int N;

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

        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        ArrayList<Integer> listForSize = new ArrayList<>();
        listForSize.add(0);

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


        for(int i = 0; i < N; i++) {
            if(listForSize.get(listForSize.size()-1) < arr[i]) {
                listForSize.add(arr[i]);
            }
            else {
                int left = 1;
                int right = listForSize.size()-1;

                while (left < right) {
                    int mid = (left + right) / 2;
                    if(listForSize.get(mid) < arr[i]) {
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                listForSize.set(right, arr[i]);
            }
        }
        System.out.println(listForSize.size() - 1);
    }
}