[백준] 12015번(Java)

📖 요세푸스 문제 0

[ 문제 ]
수열 $A$가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 $A$ = { $10, 20, 10, 30, 20, 50$ } 인 경우에 가장 긴 증가하는 부분 수열은 $A$ = { $10, 20, 10, 30, 20, 50$ } 이고, 길이는 4이다.

💡풀이

• 가장 긴 부분 수열 구하기는 이전 다른 백준 문제에서 풀었기 때문에 동일한 방식으로 풀어도 될 줄 알고 풀었더니 시간 초과가 났다.
• 가장 작은 수부터 하나씩 차례로 스택처럼 쌓다가, 다음에 오는 숫자가 제일 마지막 숫자보다 작은 경우, 내부에 해당 숫자보다 크되, 개중에 제일 작은 숫자와 대치하는 방식으로 풀이했다.
• 이 방식은 어차피 최대 개수를 세는 것이 메인이고 이들의 배열을 요구하지 않기 때문에 가능한 방식이다.
• ex) $A$ = { $10, 20, 30, 15, 20, 50$ } 인 경우,
  - $tmp$ = { $10, 20, 30$ } 까지 차례대로 넣다가, 그 다음에 오는 숫자가 15인 경우,
  - 15 보다 크되, 그 중에 제일 작은 숫자인 20과 15를 "대치"
  - $tmp$ = { $10, 15, 30$ }
  - 대치한다 해도 여전히 증가 수열의 최대 길이가 3임은 변하지 않음

package binary_search;

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

public class bj12015 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int [] A;
    static int [] tmp;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        tmp = new int[N];

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

 
        int flag = 0;
        tmp[flag] = A[0];
        for(int i = 1 ; i < N ; i ++){
            if(tmp[flag] < A[i]){
                tmp[++flag] = A[i];
            } else {
                int curloc = findloc(flag, A[i]);
                tmp[curloc] = A[i];
            }
        }
        System.out.println(flag + 1);

    }
    private static int findloc(int end, int n){
        int lo = 0;

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

            if(tmp[mid] >= n){
                end = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

}

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