[백준 11053] 가장 긴 증가하는 부분 수열 (JAVA)

백준 11053번 문제 - 가장 긴 증가하는 부분 수열

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

---

문제 분석

• 가장 긴 증가하는 부분 수열
  • 정확하게 이해를 못해 쉽게 생각 → 그냥 수가 작아지는 경우를 N에서 빼야겠다 ! : 당연히 실패
  • 가장 긴 증가하는 부분 수열 : 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수
    ex) 100 1 2 3 4 101 5 6 일 경우
    위 방식의 답은 [100, 101] 2 이고, 실제 정답은 [1, 2, 3, 4 ,5, 6] 6 이다.
• 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 출력

---

 

해결 키 포인트

 

• 어떻게 설계 할 수 있을까 ?
  • 맨 뒤부터 가능한 최장 수열 길이 구하기 방식으로 각 인덱스들의 len 구한 후, 가장 큰 len 출력
    WHY? 앞에 있는 수들은 뒤에 구해진 최장 수열 길이들로 구하면 계산이 더 간단해지므로~!
• 어떻게 구현하지 ?
  • 내가 필요한 수는 해당 숫자부터 시작했을 때 최장 수열 길이와 해당 숫자
    → Node class 만들어서 두개 다 관리하기 편하게
    + 근데 지금 생각하면 숫자 array와 len array의 index만 동일하게 해도 됬을 듯 !
  • 해당 index 이후 node들의 len 값들을 통해 현재 값의 최장 수열 길이 알아내기
  • nodes 배열에 추가 (구한 len + 1)
  • nodes 배열을 len 길이 순으로 내림차순 나열 ( 가장 큰 len 출력 : index 0번 째 )

implements Comparable<Node> {                          
      @Override                                                            
      public int compareTo(Node n) { return ~; }       
}                                                                                   

 

---

코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열의 크기(N) 입력
        int N = Integer.parseInt(br.readLine());

        // 수열 입력
        int[] nums = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        // nodes 배열은 nums[i]와 i부터 수열을 시작했을 때 최장 수열 len을 기록
        ArrayList<Node> nodes = new ArrayList<>();

        // 뒤에서부터 최장 수열 길이 확인
        for (int i = N - 1; i >= 0; i--) {
            int len = 0;

            // nodes에 있는 len 값들을 통해 현재 값의 최장 수열 길이 알아내기
            for (int j = nodes.size() - 1; j >= 0; j--) {
                Node node = nodes.get(j);

                // 만약 현재 수가 해당 node의 수보다 크고 len도 해당 수보다 클 경우 -> len 변경
                if (node.num > nums[i] && len < node.len)
                    len = node.len;
            }
            // nodes 배열에 추가
            nodes.add(new Node(nums[i], len + 1));
        }

        // nodes 배열을 len 길이 순으로 내림차순 나열
        Collections.sort(nodes);

        // 가장 큰 len 출력
        int result = nodes.get(0).len;

        bw.write(result + "\n");
        bw.flush();
        bw.close();

    }

    public static class Node implements Comparable<Node> {
        public int num;
        public int len;

        public Node(int num, int len) {
            this.num = num;
            this.len = len;
        }

        @Override
        public int compareTo(Node n) {
            return n.len - this.len;
        }
    }
}