백준 12015: 최장 증가 서브 시퀀스 2(Gold II)

by

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

12015: 최장 증가 서브 시퀀스 2

첫 번째 줄은 시퀀스 A의 크기 N(1 ≤ N ≤ 1,000,000)을 제공합니다.

두 번째 줄에는 시퀀스 A를 구성하는 Ai가 포함됩니다.

(1 ≤ Ai ≤ 1,000,000)

'추천 관련글,

www.acmicpc.net

  • 알고리즘: 이진 검색, 탐욕
  • 풀 날짜: 2023.04.19.

1) 내 솔루션(시간 초과)

2) 클래식 솔루션(두 부분 검색)

너무 멋져요!
!
!

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 {
        /** 12015_Algorithm_flow_가장 긴 증가하는 부분 수열 2: 그리디(이진 탐색) + 구현
         **/

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int() arr = new int(N);
        int() LIS = new int(N);

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

        /** 0부터 넣는 다면, 코드 통일성을 위한 것이다 **/
        // 초기화
        LIS(0) = arr(0);
        int lengthOfLIS = 1;

        for (int i = 1; i < N; i++) {
            int new_element = arr(i);

            // LIS 에 마지막 값보다 클 경우, 추가
            if (LIS(lengthOfLIS - 1) < new_element) {
                lengthOfLIS++;
                LIS(lengthOfLIS - 1) = new_element;
            } else {
                /** 삽입할 곳 이분 탐색 **/
                int start = 0;
                int end = lengthOfLIS;

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

                    // LIS(start) LIS(mid) new_element(포함) LIS(end)
                    if (LIS(mid) < new_element) start = mid + 1;
                        // LIS(start) new_element==LIS(mid)(포함) LIS(end)
                    else end = mid;
                }
                //start mid end -> start==mid end -> start == end
                /** 치환 **/
                LIS(start) = new_element;
            }
        }

        System.out.println(lengthOfLIS);
    }

}