[알고리즘] 백준 > #11053. 가장 긴 증가하는 부분 수열

얼떨결에 풀어버린 문제;

문제링크

백준 #11053. 가장 긴 증가하는 부분 수열

풀이방법

사실 이 문제말고 가장 긴 증가하는 부분 수열2를 풀라고했다. 채점하니까 시간초과가 떳고 N 범위가 더 작은 문제가 있길래 제출해봤는데 맞아버렸다;

우선순위큐를 사용했다. 가장 긴 증가하는 부분 수열이기 때문에 처음원소부터 마지막 원소까지 돌면서 전에 어떤 인덱스가 포함되었는지는 상관없고 가장 긴 증가하는 부분 수열의 가장큰 값과 비교해 해당원소가 더 크면 추가하고, 그렇지 않으면 그 다음으로 긴 부분 수열을 꺼내보는 방식으로 코드를 작성했다. 그래서 당연히 가장 긴 증가하는 부분 수열2 문제는 시간초과가 뜨고 이 문제는 맞췄다!

(그림을 막대기로 그리면서 풀이방법을 고민했더니 부분수열 내 가장 큰 값에 maxHeight라는 이름을 사용해버렸다.)

코드

import java.util.*;
public class BOJ11053 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) list.add(sc.nextInt());

        PriorityQueue<PartialSeq> q = new PriorityQueue<>();
        q.offer(new PartialSeq(0, 0));

        List<PartialSeq> tempStorage = new LinkedList<>();

        for(Integer item: list) {
            boolean isDone = false;
            while (!isDone) {
                PartialSeq head = q.poll();
                tempStorage.add(head);

                if (head.maxHeight < item) {
                    tempStorage.add(new PartialSeq(head.size + 1, item));

                    isDone = true;
                }
            }

            for (PartialSeq tempPartialSeq: tempStorage) q.offer(tempPartialSeq);
            tempStorage.clear();
        }

        System.out.print(q.peek().size);
    }
}

class PartialSeq implements Comparable<PartialSeq> {

    public int size;
    public int maxHeight;

    public PartialSeq(int size, int maxHeight) {
        this.size = size;
        this.maxHeight = maxHeight;
    }

    @Override
    public int compareTo(PartialSeq o) {
        if (this.size != o.size) return o.size - this.size; // size는 내림차순,
        else return this.maxHeight - o.maxHeight; // maxHeight는 오름차순으로 정렬
    }
}