[백준] 30805번: 사전 순 최대 공통 부분 수열

문제

백준 - 30805번: 사전 순 최대 공통 부분 수열

분석

수열 A와 수열 B가 주어졌을 때, 두 수열의 공통 부분 수열들 중 사전 순으로 가장 나중인 것을 구하는 문제이다.

문제 이름으로 인해 자칫 최장 공통 부분 수열을 떠올릴 수 있지만, 해당 문제는 공통인 것 중 가장 긴 수열이 목표이기 때문에 사전 순으로 가장 나중인 것과는 맞지 않을 수 있다.
문제의 조건을 잘 보면 N과 M 모두 100 이하이므로 숫자가 충분히 작은 것을 확인할 수 있다.
숫자가 작으므로 시간을 최적화하는 알고리즘에 구애받지 않고 단순하게 접근하는 것이 좋다.
숫자가 공통이고 가장 큰 것부터 구하고 그 이후의 위치부터 방금 작업한 것을 반복하면 최적일 것이라는 생각을 했다.
그러기 위해 A 수열과 B 수열은 각각 진행된 인덱스를 저장해야 하기 때문에 pa와 pb라는 변수를 두고 진행한다. 그리고 각 위치에서 끝까지 탐색을 돌렸을 때 공통인 최대 숫자와 위치를 갱신해 준다.
만약 공통인 숫자가 없었다면 더 이상 진행할 필요가 없으므로 중간에 끊어주는 break가 필요하다.

N이나 M (최대 100)만큼의 반복문이 3개가 중첩되어 있기 때문에 O(N^3)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		A = new int[N];
		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());
		}
		ArrayList<Integer> list = new ArrayList<>();
		int pa = 0, pb = 0;
		while (pa < N && pb < M) {
			int mx = 0, idxA = -1, idxB = -1;
			for (int i = pa; i < N; i++) {
				for (int j = pb; j < M; j++) {
					if (A[i] == B[j]) {
						if (mx < A[i]) {
							mx = A[i];
							idxA = i;
							idxB = j;
						}
					}
				}
			}
			if (idxA == -1)
				break;
			list.add(mx);
			pa = idxA + 1;
			pb = idxB + 1;
		}
		sb.append(list.size()).append("\n");
		for (int x : list) {
			sb.append(x).append(" ");
		}
		System.out.println(sb);
		br.close();
	}

}