[BOJ] 12015 가장 긴 증가하는 부분수열 2 - JAVA

1. 문제

12015번: 가장 긴 증가하는 부분 수열 2

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

---

2. 풀이

[가장 긴 증가하는 부분수열] 문제와 똑같은 방식으로 풀어서 방식은 다시 쓰지 않는다. 코드가 조금 더 간결해져서 올린다.

저번과 달라진 점은 굳이 원래의 수열을 저장하지 않은 것이다.

그리고 숫자를 입력받으면 바로 이분탐색을 이용해 경우를 나눴다.

새로 들어가야 하는 포인트가 size와 같다면 끝에 더해야하므로 add, 0보다 크다면 교체가능하니 set을 했다.

그 외의 경우는 이미 같은 숫자가 리스트에 있는 경우이므로 따로 처리하지 않았다.

import java.io.*;
import java.util.*;

public class BOJ_12015_가장긴증가하는부분수열2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      ArrayList<Integer> A = new ArrayList<>();
      StringTokenizer st = new StringTokenizer(in.readLine());

      for (int i = 0; i < N; i++) {
         int num = Integer.parseInt(st.nextToken());
         int idx = -Collections.binarySearch(A, num) - 1;
         if (idx == A.size()) A.add(num);
         else if (idx >= 0) A.set(idx, num);
      }

      System.out.println(A.size());
   }
}

 

---

3. 결과