[Baekjoon] 11053번 가장 긴 증가하는 부분 수열 (Java)

예제 입력1

6
10 20 10 30 20 50

예제 출력1

4

 

 

 

package Q11053;

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

public class Main {
	public static String[] str;
	public static int num;
	public static ArrayList<Integer> arr = new ArrayList<Integer>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine());
		str = new String[num];

		str = br.readLine().split(" "); 	// 입력 받은 값 줄 별로 split해서 str[i]에 저장
		
		ArrayList<Integer> arr = search();
		Collections.sort(arr, Collections.reverseOrder());	// 내림차순 정렬
		System.out.println(arr.get(0));
	}
	
	public static ArrayList<Integer> search() {
		ArrayList<Integer> arr = new ArrayList<Integer>();
		for(int i = 0; i < num; i++) {
			arr.add(1);
			for(int j = 0; j < i; j++) {	// 내 이후는 탐색할 필요가 없음
				// arr.get(j)+1 > arr.get(i) -> 현재 내 증가하는 수열 길이보다 이전 길이 +1이 더 크다면
				// Integer.parseInt(str[j]) < Integer.parseInt(str[i]) -> 내 이전 숫자 보다 내가 더 크면
				if(arr.get(j)+1 > arr.get(i) && Integer.parseInt(str[j]) < Integer.parseInt(str[i])) {
					arr.set(i, arr.get(j)+1);	// 현재 값을 이전 길이+1로 바꿈
				}
			}
			System.out.print(arr.get(i) + " ");
		}
		return arr;
	}
}

정말 문제 이해가 가장 힘들었던 문제....

처음에는 내 순서가 오기 전까지 나보다 작은 숫자들이 몇 개나 있는가인 줄 알았는데,

전혀 아니었다 ~ 문제 이해를 이렇게 못하다니 반성 좀 해야겠다