[자바] 백준 12738 - 가장 긴 증가하는 부분 수열 3 (java)

 문제 : boj12738

---

 

필요 알고리즘 개념

•  LIS (Longest Increasing Subsequence; 가장 긴 증가하는 부분 수열)
  • LIS 알고리즘을 사용해 푸는 문제이다.
• 이분탐색, 매개변수 탐색법(parametric search)
  
  • LIS 알고리즘 구현을 위해 가장 중요한건 이분탐색에서 그보다 큰 가장 작은 값 혹은 그보다 작은 가장 큰 값을 알 수 있는 매개변수 탐색법이다. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  LIS 알고리즘 기본형태의 문제로, LIS 알고리즘을 공부한 후 그대로 구현하면 된다. 자바의 경우 Collection에서 이분탐색을 제공해주긴 하나, 코드가 상당히 지저분한 편이라 ㅋㅋ 직접 이분탐색을 구현하는게 가장 깔끔한 편이긴 하다.

 

  제일 간단하게 구현가능한건 역시나 이분 트리로 구현되어 있는 TreeSet을 활용하는 방법이다. 이하 Collections.binarySearch와 TreeSet을 이용한 방법으로 코드를 작성해두었다. TreeSet의 경우엔 remove()가 시간을 좀 잡아먹는 편이라 시간상으론 binarySearch를 쓰는게 더 이득이다.

 

---

 

코드(이분탐색으로 구현) : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> bs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(st.nextToken()) + 1000000000;
            if (bs.isEmpty() || bs.get(bs.size()-1) < cur) {
                bs.add(cur);
                continue;
            }
            int idx = Collections.binarySearch(bs, cur);
            int targetIdx = idx>=0?idx:-idx-1;
            bs.set(targetIdx, cur);
        }
        System.out.println(bs.size());
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드(트리셋으로 구현) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(Integer.parseInt(st.nextToken()));
        for (int i = 1; i < n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (ts.last() >= cur) {
                ts.remove(ts.ceiling(cur));
            }
            ts.add(cur);
        }
        System.out.println(ts.size());
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}