b14003. 가장 긴 증가하는 부분수열 5

 

https://www.acmicpc.net/problem/14003

 

 

 

📌 자바(Java)로 푸는 가장 긴 증가하는 부분 수열 5 - 백준 14003 🔼

LIS + 경로 추적을 O(N log N)으로 해결하는 대표 문제

 

 

🔎 문제 개요

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

수열이 주어졌을 때,

 

1. 가장 긴 증가하는 부분 수열의 길이
2. 해당 부분 수열 자체

 

를 구하는 문제입니다.

단, 수열의 길이가 최대 100만 개이므로 O(N²) 풀이 불가능합니다.

 

---

💡 예제 입력

6
10 20 10 30 20 50

 

💡 예제 출력

4  
10 20 30 50

 

 

---

🛠 알고리즘 접근 방식

 

 

✅ 핵심 전략: 이진 탐색 기반 LIS + 경로 추적

 

• list[]: 현재까지 만든 LIS 수열 (값만 추적)
• dp[i]: arr[i]가 LIS의 몇 번째 위치인지
• prev[i]: LIS 경로를 재구성하기 위한 이전 인덱스
• lastIndex[length]: 해당 길이의 LIS에서 마지막으로 들어온 인덱스

 

---

🔹 Java 코드 설명

 

 

📌 LIS 초기값 설정

list[0] = arr[0];
dp[0] = 1;
prev[0] = -1;
lastIndex[0] = 0;

✔ 첫 번째 원소를 LIS의 시작으로 설정

📌 LIS 진행 & 이진 탐색으로 위치 계산

if (val > list[top]) {
    list[++top] = val;
    dp[i] = top + 1;
    prev[i] = lastIndex[top - 1];
    lastIndex[top] = i;
} else {
    int left = 0, right = top;
    while (left < right) {
        int mid = (left + right) / 2;
        if (list[mid] >= val) right = mid;
        else left = mid + 1;
    }
    list[left] = val;
    dp[i] = left + 1;
    prev[i] = (left == 0) ? -1 : lastIndex[left - 1];
    lastIndex[left] = i;
}

✔ 수열을 순회하며

✔ list는 값만 저장하고

✔ prev, dp, lastIndex를 통해 경로 복원 정보 저장

📌 경로 복원

int[] result = new int[top + 1];
int resultIdx = top;
int idx = lastIndex[top];
while (idx != -1) {
    result[resultIdx--] = arr[idx];
    idx = prev[idx];
}

✔ lastIndex[top]에서부터 거슬러 올라가며 경로 복원

✔ prev[]를 따라가면서 수열 역추적

✔ 역순으로 배열에 저장 후 출력

---

🏆 정리

✅ 핵심 포인트

 

• O(N log N) LIS 알고리즘에 경로 추적용 인덱스 배열 추가
• 마지막 인덱스를 기억해두고 역추적하면 실제 수열도 구할 수 있음
• 백준 14002보다 입력 사이즈가 크므로 효율성 필수