BOJ_사전 순 최대 공통 부분 수열 _30805 (Java)

문제 링크

성능 요약

메모리: 15160 KB, 시간: 120 ms

분류

그리디 알고리즘

제출 일자

2025년 1월 1일 22:36:13

문제 설명

어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.

해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
예를 들어, $\{1,1,5\}$는 $\{3,\underline{\color{blue} 1} ,4,\underline{\color{blue} 1} ,\underline{\color{blue} 5} ,9\}$의 부분 수열이지만, $\{1,5,1\}$의 부분 수열은 아닙니다.
또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.

두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
길이가 $0$인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.
양의 정수로 이루어진 길이가 $N$인 수열 $\{A_1,\cdots ,A_N\}$이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 $M$인 수열 $\{B_1,\cdots ,B_M\}$이 주어집니다.

수열 $A$와 수열 $B$가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.

입력

첫 줄에 수열 $A$의 길이 $N$이 주어집니다. $(1 \le N \le 100)$ 
둘째 줄에 $N$개의 양의 정수 $A_1,A_2,\cdots,A_N$이 주어집니다. $(1 \le A_i \le 100)$ 
셋째 줄에 수열 $B$의 길이 $M$이 주어집니다. $(1 \le M \le 100)$ 
넷째 줄에 $M$개의 양의 정수 $B_1,B_2,\cdots,B_M$이 주어집니다. $(1 \le B_i \le 100)$ 

출력

$A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 $K$를 출력하세요.

$K \ne 0$이라면, 다음 줄에 $K$개의 수를 공백으로 구분해 출력하세요. $i$번째 수는 $A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 $i$번째 수입니다.

느낀점

• 최대 공통 부분 수열이라고 해서 복잡하게 생각했지만, ‘사전순’이라는 조건으로 더 간단한 문제가 되었다.
• 최대 공통 부분 수열 풀이 방법으로 먼저 접근해서 반례찾는데에도 시간이 걸렸다. 차라리 몰랐다면 더 쉬웠을수도,,
• 질문게시판을 많이 찾아봤는데 실제 코테에서는 테스트 케이스를 질문할 수 없으니, 스스로 테케를 만들고 테스트해보는 연습이 필요할 것 같다.

설계 : 15분

• 결론: 두 수열에서 공통된 수 중 가장 큰 수를 찾고 해당 인덱스 이후부터 다시 같은 방법을 반복해 찾아진 가장 큰 수들로 수열을 이룬다.
• 처음에는 최대 공통 부분 수열을 찾는 로직을 사용했는데, 최대 공통 부분 수열과 사전순 최대 공통 부분 수열은 완전히 달랐다.
• 최대 공통 부분 수열내에서 사전순을 찾는게 아니다. 원리를 생각하면 그냥 가장 큰 수부터 찾는게 사전순으로 더 나중인 것이다.

코드(Java)

• 구현 시간: 90분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 사전 순 최대 공통 부분 수열_30805
 * Date: 2025.01.01
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

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

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] A = input();
        int[] B = input();
        int n = A.length - 1;
        int m = B.length - 1;

        int idx_A = 1;
        int idx_B = 1;
        Queue<Integer> word = new ArrayDeque<>();

        while (idx_A <= n && idx_B <= m) {
            int result = 0;
            for (int i = idx_A; i <= n; i++) {
                for (int j = idx_B; j <= m; j++) {
                    if (A[i] == B[j]) result = Math.max(result, A[i]);
                }
            }

            if (result != 0) {
                word.offer(result);
                while (A[idx_A] != result) idx_A++;
                while (B[idx_B] != result) idx_B++;
                idx_A++;
                idx_B++;
            } else break;
        }

        StringBuilder sb = new StringBuilder();
        sb.append(word.size()).append("\n");
        while (!word.isEmpty()) sb.append(word.poll()).append(" ");
        bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

    private static int[] input() throws IOException {
        int size = Integer.parseInt(br.readLine());
        int[] arr = new int[size+1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        return arr;
    }
}