방과후
ALGORITHM NOTE약 2분

BOJ 30805 - 사전 순 최대 공통 부분 수열

전자 사전 가져와

#algorithm#boj#gold#greedy
아카이브로 돌아가기

문제 링크

문제

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

  • 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
  • 예를 들어, 수열 1, 1, 5는 3, 1, 4, 1, 5, 9에서 1 -> 1 -> 5를 순서대로 고르면 되므로 부분 수열이지만, 1, 5, 1은 같은 방식으로 고를 수 없으므로 부분 수열이 아닙니다.

또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.

  • 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
  • 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
  • 길이가 0인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.

양의 정수로 이루어진 길이가 N인 수열 A₁, ..., Aₙ이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 M인 수열 B₁, ..., Bₘ이 주어집니다.

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

입력

첫 줄에 수열 A의 길이 N이 주어집니다. (1 <= N <= 100)

둘째 줄에 N개의 양의 정수 A₁, A₂, ..., Aₙ이 주어집니다. (1 <= Aᵢ <= 100)

셋째 줄에 수열 B의 길이 M이 주어집니다. (1 <= M <= 100)

넷째 줄에 M개의 양의 정수 B₁, B₂, ..., Bₘ이 주어집니다. (1 <= Bᵢ <= 100)

출력

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

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

풀이

사전 순으로 가장 큰 공통 부분 수열을 만들려면 현재 위치 이후에서 공통으로 만들 수 있는 값 중 가장 큰 값을 먼저 골라야 한다. 앞자리가 커지는 순간 뒤 선택보다 항상 우선한다.

코드에서는 현재 포인터 이후 구간을 훑으며 양쪽에 공통으로 존재하는 최댓값을 찾고, 그 값을 결과에 넣은 뒤 두 수열의 포인터를 다음 위치로 넘긴다. 더 이상 공통 값이 없을 때까지 반복하면 된다.

즉 길이 최대 LCS를 구하는 DP와는 다르게, 앞자리부터 사전 순 최대를 보장하는 값을 하나씩 확정하는 그리디에 가깝다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
	
	private static int N, M;
	private static int[] A, B;
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		A = input();
		N = A.length;
		B = input();
		M = B.length;
		
		Queue<Integer> q = solve();
		sb.append(q.size()).append('\n');
		for (int num : q) 
			sb.append(num).append(" ");
		System.out.println(sb);
	}
	
	private static int[] input() throws IOException {
		int N = Integer.parseInt(br.readLine());
		int [] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) 
			arr[i] = Integer.parseInt(st.nextToken());
		
		return arr;
	}
	
	private static Queue<Integer> solve() {
		int idxA = 0, idxB = 0;
		Queue<Integer> q = new ArrayDeque<>();
		
		while (idxA <= N && idxB <= M) {
			int maxInt = 0;
			
			for (int i = idxA ; i < N; i++) {
				for (int j = idxB; j < M; j++) {
					if (A[i] == B[j]) maxInt = Math.max(maxInt, A[i]);
				}
			}
			
			if (maxInt == 0)
				break;
			
			q.offer(maxInt);
			while(A[idxA] != maxInt) idxA++;
			while(B[idxB] != maxInt) idxB++;
			idxA++; idxB++;
		}
		
		return q;
	}
}

복잡도

  • 시간 복잡도: 정답 길이를 LL이라 하면 매 단계 남은 두 수열을 비교하므로 O(NML)O(NML)이다.
  • 공간 복잡도: 정답 큐와 입력 배열을 저장하므로 O(N+M+L)O(N + M + L)이다.

마무리

이번 문제는 길이보다 사전 순이 더 중요하다. 그래서 DP보다 현재 이후의 최대 공통값을 고르는 그리디 관점이 더 잘 맞는다.