[JAVA] 백준 3745번 : 오름세

 

---

 

• 코드

정답 코드 : 계속해서 증가하는 부분수열을 찾는 것이 LIS 같아서 LIS 알고리즘을 활용하여 구현하였다.

 

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        
        while((s=br.readLine())!=null) {
        	s = s.trim();		//이걸 안해주면 runtime이 뜬다. 질문 검색에서 알려줘서 이렇게 했는데 잘모르겠음.
            int n = Integer.parseInt(s);
            int[] array = new int[n+1];
            int[] LIS = new int[n+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=1;i<=n;i++) {
                array[i] = Integer.parseInt(st.nextToken());
            }
            LIS[0] = array[0];
            int count = 0;
            for(int i=1;i<=n;i++) {
                int idx = binary(LIS, 1,count+1,array[i]);
                LIS[idx] = array[i];
                if(idx == count+1) count++;
            }
            System.out.println(count);
        }
    }
    private static int binary(int[] LIS, int startIndex,int endIndex,int key) {
        while(startIndex<endIndex) {
            int mid = (startIndex+endIndex) /2;
            if(LIS[mid]<key) startIndex = mid + 1;
            else endIndex = mid;
        }
        return endIndex;
    }
}