[Baekjoon] 사전 순 최대 공통 부분 수열

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

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

public class Main {
    private static StringBuilder answer = new StringBuilder();
    private static int N, M;
    private static int[] A, B;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    private static void sol() {
        List<Integer> result = new ArrayList<>();

        int aIndex = 0;
        int bIndex = 0;

        while (true) {
            int max = -1;
            int aIdx = -1;
            int bIdx = -1;

            for (int i = aIndex; i < N; i++) {
                for (int j = bIndex; j < M; j++) {
                    if (A[i] == B[j] && A[i] > max) {
                        max = A[i];
                        aIdx = i;
                        bIdx = j;
                    }
                }
            }

            if (max == -1) {
                break;
            }

            result.add(max);
            aIndex = aIdx + 1;
            bIndex = bIdx + 1;
        }

        answer.append(result.size()).append("\n");
        for (int i : result) {
            answer.append(i).append(" ");
        }
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A = new int[N];

        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());
        B = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.close();
    }
}

주요 개념

• 그리디

풀이 방법

• 초기에는 모든 공통 부분 수열을 구하는 로직을 생각했다.

  • 하지만 문제 조건에서 사전순 가장 나중이라는 조건이 있기 때문에 모든 경우의 수를 구하는 것이 아닌, 가장 큰 수를 기준으로 찾는다.

  • 수열이 다음과 같이 존재한다고 하더라도 A : 123456789 B : 123456789 가장 큰 수열은 9 이다.

  • 따라서 while문 내부에서 매 탐색마다 가장 큰 공통 숫자를 찾는다.

    • 다음 반복에서는 해당 공통 숫자 다음 인덱스부터 탐색하도록 한다.