[BOJ 12015] 가장 긴 증가하는 부분수열2(LIS)

문제

• BOJ 12015
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

이 문제는 이분탐색으로 풀 수 있고 접근한 순서는 다음과 같다.

1. 넣어줘야 하는 값num이 현재 리스트의 마지막값보다 크면 그 뒤에 바로 넣어준다.

   if (num > ans.get(ans.size() - 1)) ans.add(num);
   

2. 만약 작거나 같다면 이분탐색을 해서 위치를 찾아준다.

 int left = 0;
 int right = ans.size() - 1;
 int mid = 0;

 while (left < right) {
   mid = (left + right) / 2;
      if(ans.get(mid) >= num) right = mid; //mid앞부분에 넣어줘야 하니까
      else left = mid + 1; //mid뒷부분에 넣어줘야 하니까
 }//End 이분탐색
 ans.set(right, num);  

길이만 구해주기 때문에 현재 리스트에 들어있는 값과 중복된 값은 고려하지 않아도 되므로 리스트의 set()함수를 사용해주었다.

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N;
    static List<Integer> ans; //LIS

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        ans = new ArrayList<>();
        ans.add(0); //초기에 0넣어주기

        /*LIS 만들기
         * 1. 리스트에서 가장 마지막 값보다 크면 넣어줌
         * 2. 작거나 같으면 이분탐색해서 자리 찾아주기
         * */

        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            if (num > ans.get(ans.size() - 1)) ans.add(num);
            else { //num을 넣어줄 인덱스를 이분탐색
                int left = 0;
                int right = ans.size() - 1;
                int mid = 0;

                while (left < right) {
                    mid = (left + right) / 2;
                    if(ans.get(mid) >= num) right = mid; //mid앞부분에 넣어줘야 하니까
                    else left = mid + 1; //mid뒷부분에 넣어줘야 하니까
                }//End 이분탐색
                ans.set(right, num);
            }
        }//End input
        System.out.println(ans.size()-1); //맨 처음 0빼고
    }
}