문제 링크

성능 요약

메모리: 184056 KB, 시간: 780 ms

분류

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

제출 일자

2025년 2월 28일 16:37:14

문제 설명

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

풀이

느낀점

• 인덱스를 정확히 사용하는 연습을 좀 더 해야겠다고 느꼈다.
• 풀이 접근은 괜찮았는데, 인덱스 문제로 디버깅 시간이 오래걸렸다.
• 그래도 직접 테케를 만들어서 질문게시판 참고 안하고 디버깅에 성공한 점이 좋았다.

설계 : 20분

• 가장 긴 증가하는 부분 수열 3 문제처럼 빠르게 길이를 구하면서 가장 마지막 숫자의 실제 입력된 순서를 갱신해가며 저장해둔다. 각 입력된 순서대로 해당 숫자까지의 가장 긴 부분수열 길이도 저장한다.
• 모두 구했다면 마지막 숫자의 실제 인덱스부터 역방향으로 순회하며 실제 가능한 경우의 수를 찾는다.
  • maxIdx, idx를 두고 maxIdx의 숫자보다 작고, 기록된 부분수열 길이가 1만큼 더 짧은 수를 찾는다.(idx)
  • 수를 찾았다면 해당 idx를 maxIdx에 대입하여 갱신하고 idx-1 해서 다음 숫자를 찾는다.
  • 찾은 수들을 거꾸로 출력한다. (배열과 스택을 사용해봤지만 스택이 아주 조금 더 빨랐음, 의미있는 차이는 아니었다.)

코드(Java)

• 구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 가장 긴 증가하는 부분 수열 5_문제번호
 * Date: 2025.02.28
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[] dp;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
        dp = new int[n];            // 빠른 dp 갱신용
        int[] nums = new int[n];    // 실제 순서대로 입력된 수
        int[] length = new int[n];  // 실제 순서대로 입력된 각 수까지의 증가수열 길이
        int maxIdx = 0;             // 가장 긴 증가하는 부분 수열 마지막 숫자의 실제 순서
        int dpIdx = 1;              // 지금까지의 가장 긴 증가하는 부분 수열 길이

        st = new StringTokenizer(br.readLine(), " ");
        nums[0] = Integer.parseInt(st.nextToken());
        dp[0] = nums[0];
        length[0] = 1;

        for (int i = 1; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            if (nums[i] > dp[dpIdx-1]) {
                dp[dpIdx++] = nums[i];
                length[i] = dpIdx;
                maxIdx = i;
            } else {
                length[i] = findIdx(nums[i], dpIdx-1) + 1;
                dp[length[i]-1] = nums[i];
            }
        }

        bw.write(String.valueOf(dpIdx) + "\n");

        Stack<Integer> stack = new Stack<>();
        stack.add(nums[maxIdx]);
        int cnt = dpIdx - 1;    // 더 찾아야 하는 개수
        int idx = maxIdx - 1;   // 탐색할 인덱스
        while (cnt > 0 && idx >= 0) {
            while (nums[idx] >= nums[maxIdx] || length[idx] != length[maxIdx] - 1) {
                idx--;
            }
            stack.add(nums[idx]);
            maxIdx = idx--;
            cnt--;
        }

        while (!stack.isEmpty()) bw.write(String.valueOf(stack.pop()) + " ");
		bw.flush();
		bw.close();
		br.close();
	}

    public static int findIdx(int num, int h) {
        int low = 0;
        int high = h;
        int mid;
        while (low < high) {
            mid = (low + high) / 2;
            if (dp[mid] > num) high = mid;
            else if (dp[mid] < num) low = mid + 1;
            else if (dp[mid] == num) return mid;
        }
        return high;
    }
}