[BOJ] 14003 가장 긴 증가하는 부분 수열 5 - JAVA

1. 문제

14003번: 가장 긴 증가하는 부분 수열 5

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

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

---

2. 풀이

탐색

1.  원본 수열 A는 array에 저장하고, 각 요소 별 list에 담은 인덱스 순서를 index에 저장한다.

2.  숫자 하나를 입력받고, 그 숫자가 list의 어떤 위치에 있어야 하는지 찾는다. 만약 binarySearch 결과가 0보다 작다면 원래 들어가야 할 위치인 -idx-1로 바꾼다. 

3.  idx가 list 사이즈와 동일하다면 add, 그보다 작다면 list.set을 사용해 list를 변경한다.

4.  index[i]에 A 수열 i번째 요소를 몇 번째 인덱스로 집어넣었는지 저장한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
StringTokenizer st = new StringTokenizer(in.readLine());

ArrayList<Integer> list = new ArrayList<>();
int[] array = new int[N];
int[] index = new int[N];

int num, idx;
for(int i=0;i<N;i++){
   num = Integer.parseInt(st.nextToken());
   array[i] = num;

   idx = Collections.binarySearch(list, num);
   if(idx < 0) idx = -idx-1;

   if(idx == list.size()) list.add(num);
   else list.set(idx,num);

   index[i] = idx;
}

 

답 찾기

list.size는 가장 긴 증가하는 부분수열의 길이고, 그 요소는 답과 무관하다.

index에 저장된 값을 이용해서 뒤에서부터 답을 찾아내면 된다.

 

1.  스택을 이용했다. LIFO방식이기 때문이다.

2.  처음 인덱스번호를 list.size-1로 지정하고, A수열 마지막 부터 index[i]가 idx와 동일한 것을 찾는다.

3.  만약 동일한 것을 찾았다면 stack에 array[i]를 추가하고, 다음 인덱스를 찾기 위해 idx-1한다.

4.  탐색이 끝나면 stack을 pop시키며 sb에 추가한다.

array	10	20	10	30	50
index	0	1	0 (idx=1과 동일하지 않아서 무시된다.)	2	3

StringBuilder sb = new StringBuilder();
sb.append(list.size()).append('\n');

Stack<Integer> stack = new Stack<>();
idx = list.size()-1;
for(int i=N-1;i>=0;i--){
   if(index[i] != idx) continue;
   stack.push(array[i]);
   --idx;
}

while(!stack.empty()) sb.append(stack.pop()).append(' ');
System.out.println(sb);

 

전체 코드

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

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

      ArrayList<Integer> list = new ArrayList<>();
      int[] array = new int[N];
      int[] index = new int[N];

      int num, idx;
      for(int i=0;i<N;i++){
         num = Integer.parseInt(st.nextToken());
         array[i] = num;

         idx = Collections.binarySearch(list, num);
         if(idx < 0) idx = -idx-1;

         if(idx == list.size()) list.add(num);
         else list.set(idx,num);

         index[i] = idx;
      }

      StringBuilder sb = new StringBuilder();
      sb.append(list.size()).append('\n');

      Stack<Integer> stack = new Stack<>();
      idx = list.size()-1;
      for(int i=N-1;i>=0;i--){
         if(index[i] != idx) continue;
         stack.push(array[i]);
         --idx;
      }

      while(!stack.empty()) sb.append(stack.pop()).append(' ');
      System.out.println(sb);
   }
}

---

3. 결과

DP를 이용한 방식은 메모리초과가 있을 수 있어 ArrayList를 이용한 방식을 사용했다.

ArrayList를 계속 갱신하면서 사용하기 때문에 그 요소가 정답이 아닐 수 있다는 걸 뒤늦게 알고 방식을 수정했다.

 

java 8, 11, 15 세 버전을 선택할 수 있어서 동일한 코드를 세 번 채점해봤는데 8과 11,15가 메모리면에서 아주 큰 차이가 있었다. 이 부분은 나중에 확인해봐야할 것 같다.