[백준 #14003] 가장 긴 증가하는 부분 수열 5 - JAVA [자바]

분류

이분 탐색, 가장 긴 증가하는 부분 수열: O(n log n)

 

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

예제 입력

6
10 20 10 30 20 50

 

예제 출력

4
10 20 30 50

코드 - 가장 긴 증가하는 부분 수열 5.java

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

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 수열의 크기 N
        int[] num = new int[N]; // 수열을 저장하는 배열
        int[] dp = new int[N]; // 각 숫자가 가장 긴 증가하는 부분 수열에 포함되었을 때의 길이를 저장하는 배열
        List<Integer> L = new ArrayList<>(); // 가장 긴 증가하는 부분 수열(LIS)를 저장하는 리스트
        Stack<Integer> s = new Stack<>(); // 역추적을 위한 스택
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int idx = 0, dptmp = 0; // idx는 LIS의 마지막 원소의 위치를, dptmp는 LIS의 길이를 저장
        for (int i = 0; i < N; i++) {
            int a = Integer.parseInt(st.nextToken());
            num[i] = a; // 입력받은 숫자를 num 배열에 저장
            if (L.isEmpty()) {
                L.add(num[i]); // LIS가 비어있다면, 현재 숫자를 추가
                dp[i] = 1; // 현재 숫자가 LIS에 포함되었을 때의 길이는 1
            } else {
                if (L.get(L.size() - 1) < num[i]) {
                    L.add(num[i]); // LIS의 마지막 숫자보다 현재 숫자가 크다면, 현재 숫자를 추가
                    dp[i] = L.size(); // 현재 숫자가 LIS에 포함되었을 때의 길이를 저장
                } else {
                    int pos = Collections.binarySearch(L, num[i]); // 이분 탐색을 통해 현재 숫자가 들어갈 위치를 찾음
                    if (pos < 0) pos = -(pos + 1); // 이분 탐색 결과가 음수라면, -(pos + 1)을 통해 적절한 위치로 변환
                    L.set(pos, num[i]); // LIS를 갱신
                    dp[i] = pos + 1; // 현재 숫자가 LIS에 포함되었을 때의 길이를 저장
                }
            }
            if (dp[i] > dptmp) {
                idx = i; // LIS의 마지막 원소의 위치를 갱신
                dptmp = dp[i]; // LIS의 길이를 갱신
            }
        }
        System.out.println(L.size()); // LIS의 길이 출력
        s.push(num[idx]); // LIS의 마지막 원소를 스택에 추가
        for (int i = idx - 1; i >= 0; i--) {
            if (num[i] < num[idx] && dp[i] + 1 == dp[idx]) {
                idx = i; // LIS의 이전 원소의 위치로 갱신
                s.push(num[i]); // LIS의 이전 원소를 스택에 추가
            }
        }
        while (!s.isEmpty()) {
            System.out.print(s.pop() + " "); // 스택이 비어있지 않은 동안, 스택의 상단 원소를 출력하고 제거. 이는 LIS를 역순으로 출력하는 과정입니다.
        }
    }
}

 

 

코드 분석하기

위의 코드는 "가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)"를 찾는 문제를 해결하기 위해 이분 탐색(Binary Search)를 사용합니다. 이분 탐색은 정렬된 데이터에서 특정 값을 효율적으로 찾는 알고리즘으로, 탐색 범위를 절반씩 줄여나가며 값을 찾습니다.

1. num 배열: 주어진 수열을 저장하는 배열입니다.
2. dp 배열: 각 위치에서의 최대 증가 부분 수열의 길이를 저장합니다.
3. L 리스트: 현재까지 확인한 원소들로 만들 수 있는 가장 긴 증가하는 부분 수열(LIS)을 저장합니다. 이 리스트의 마지막 원소는 항상 가장 큰 값이 됩니다.
4. s 스택: 가장 긴 증가하는 부분 수열을 역순으로 저장합니다. 이 스택의 원소를 하나씩 꺼내면 원하는 부분 수열을 얻을 수 있습니다.

각 원소를 확인하면서 이분 탐색을 통해 L 리스트에 추가할 위치를 찾습니다. 만약 현재 원소가 L 리스트의 마지막 원소보다 크다면, 현재 원소를 리스트의 끝에 추가하고 dp 배열에는 L 리스트의 크기를 저장합니다. 그렇지 않다면, 이분 탐색을 통해 현재 원소가 들어갈 위치를 찾고, 그 위치의 원소를 현재 원소로 교체합니다. 그리고 dp 배열에는 L 리스트에서 현재 원소의 위치를 저장합니다.

이 과정을 거치면, L 리스트는 가장 긴 증가하는 부분 수열이 되고, dp 배열은 각 위치에서의 최대 증가 부분 수열의 길이를 저장하게 됩니다. 이 정보를 이용하여 스택을 사용해 원하는 부분 수열을 역순으로 찾을 수 있습니다.

 

이분 탐색(Binary Search)에 대한 설명:

이분 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 효율적으로 찾는 알고리즘입니다. 주어진 값과 중간점의 값이 같다면 찾고자 하는 값이 있음을 알 수 있습니다. 주어진 값이 중간점의 값보다 크다면 중간점의 오른쪽을, 작다면 중간점의 왼쪽을 탐색합니다. 이를 반복하여 원하는 값을 찾습니다. 이분 탐색의 시간 복잡도는 O(log n)입니다. 이 알고리즘은 정렬된 데이터에서 효율적으로 값을 찾을 때 매우 유용합니다.

 

 

백준에서 문제 풀어보기

 

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

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