[Algorithm] 백준 LIS 문제 - 가장 긴 증가하는 부분 수열 5(14003) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 LIS 문제 - 가장 긴 증가하는 부분 수열5 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/14003

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

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        int[] arr = new int[n]; // 입력 배열
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) arr[i] = parseInt(st.nextToken()); // 배열 초기화
        List<Integer> result = search(arr);
        
        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append("\n");
        for (Integer i : result) sb.append(i).append(" ");
        System.out.print(sb);
    }
    
    static List<Integer> search(int[] arr) {
        List<Integer> dp = new ArrayList<>();
        
        int[] idxs = new int[arr.length]; // 인덱스 저장
        int[] preIdxs = new int[arr.length]; // 다음으로 이동할 임시 인덱스
        
        for (int i = 0; i < arr.length; i++) {
            if (dp.isEmpty() || arr[i] > dp.get(dp.size() - 1)) {
                if (!dp.isEmpty()) preIdxs[i] = idxs[dp.size() - 1]; // dp가 비지 않은 경우 업데이트하는 인덱스와 다음으로 이동할 인덱스 업데이트
                dp.add(arr[i]); // dp에 추가
                idxs[dp.size() - 1] = i; // 인덱스 업데이트
            } else { // 이분 탐색
                int left = 0, right = dp.size() - 1;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (dp.get(mid) < arr[i]) left = mid + 1;
                    else right = mid;
                }
                dp.set(right, arr[i]);
                idxs[right] = i;
                if (right > 0) preIdxs[i] = idxs[right - 1];
            }            
        }
        
        List<Integer> lis = new ArrayList<>();
        int idx = idxs[dp.size() - 1];
        while (lis.size() < dp.size()) {
            lis.add(arr[idx]);
            idx = preIdxs[idx];
        }
        Collections.reverse(lis); // 마지막 역순 출력
        return lis;
    }
}

 

2. 풀이 중점 사항

 

해당 문제는 이전에 풀었던 LIS 풀이에서 자세하게 설명하였습니다!

해당 풀이에서 그림과 함께 자세하게 설명하여서 링크를 남기도록 하겠습니다!

https://gose-kose.tistory.com/103

[Algorithm] 백준 DP 문제 - 줄세우기(2631) 자바 풀이

이상으로 풀이를 마치겠습니다 감사합니다!