백준 14002 자바 - 가장 긴 증가하는 부분 수열 4 (BOJ 14002 JAVA)

문제 : boj14002

 

  

  가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘에 대한 설명은 생략하고, 가능한 수열을 찾는 방법에 대해 설명한다.

 

 

1.

  LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제 정답은 '10 20 30'이므로 LIS 알고리즘 자체만 사용해서는 원하는 실제 수열을 출력할 수 없다.

 

2.

  추가로 배열을 더 사용해서 이번엔 각 입력값이 LIS 알고리즘에서 몇 번 인덱스에 들어가게 되는지 확인해보자. indexOrder라는 배열에 넣어봤다. 예를들어 3번째 입력값인 30에서 indexOrder가 '2'인 것은 bs 배열 인덱스 2번 위치에 해당 숫자가 들어갔다는 의미이다.

 

3.

  그럼 이걸 가지고 어떻게 LIS의 실제값을 찾아낼 수 있을까? indexOrder를 역순으로 보면서 큰 인덱스 순서대로 걸러내면 된다. 예를들어 LIS길이가 3이므로 가장 큰 인덱스는 0,1,2 중 2가 될 것이다. 역순으로 보면서 인덱스 역순으로 2,1,0 인덱스를 찾아서, 찾으면 바로바로 답으로 선택하면 된다.

 

  '10 20 30 5 15 25' 와 같은 경우, indexOrder는 순서대로 '0 1 2 0 1 2'가 될 것이다. 사실 이 경우라면 역순으로 살펴보며 어떠한 2->1->0을 선택해도 답이 될 수 있다. 예를들어 '10 20 25'도 답이고, '10 15 25'도 답이고 '5 15 25'도 답이다. 하지만 이러한 상황이 매번 나타날 순 없다. 모든 상황을 만족시키려면 모든 케이스를 만족할 만한 로직을 찾아야 한다.

 

 

4.

  indexOrder를 순서대로 보면서 인덱스도 증가하는 순서대로 찾거나, 위에서 설명한대로 역순으로 감소하는 순서대로 찾긴 한데, 바로바로 고르지 않고 아무거나 고르는 경우에 대한 반례를 들어보겠다.

 

   '100 50 200 30 40 150 300' 에 대해 그려보겠다.

  위의 경우 indexOrder를 역순으로 index가 감소하는 순서로 바로바로 찾아낸 결과인 '30 40 150'을 제외한 모든 선택은 답이 될 수 없음을 알 수 있다('100 200 150', '50 40 150' 등 모두 답이 안됨).

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int[] inputData = new int[n];
        ArrayList<Integer> bs = new ArrayList<>();
        int[] idxOrder = new int[n];
        for (int i = 0; i < n; i++) {
            int cur = nextInt();
            inputData[i] = cur;
            if (bs.isEmpty() || bs.get(bs.size()-1) < cur) {
                idxOrder[i] = bs.size();
                bs.add(cur);
                continue;
            }
            int idx = Collections.binarySearch(bs, cur);
            idxOrder[i] = idx>=0?idx:-idx-1;
            bs.set(idxOrder[i], cur);
        }

        int[] result = new int[bs.size()];
        int resultIdx = 0;
        int idx = n;
        n = bs.size();
        while (n-->0) {
            while (--idx>=0) {
                if (idxOrder[idx] == n) {
                    result[resultIdx++] = inputData[idx];
                    break;
                }
            }
        }

        StringBuilder answer = new StringBuilder();
        answer.append(bs.size()).append('\n');
        for (int i = result.length-1; i >= 0; i--)
            answer.append(result[i]).append(' ');
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}