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

문제

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

• 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
• 예를 들어, {1,1,5}는 {3,1,4,1,5,9}의 부분 수열이지만, {1,5,1}의 부분 수열은 아닙니다.

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

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

양의 정수로 이루어진 길이가 N인 수열 {A1,⋯,AN}이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 M인 수열 {B1,⋯,BM}이 주어집니다.

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

입력

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

둘째 줄에 N개의 양의 정수 A1,A2,⋯,AN이 주어집니다. (1≤Ai≤100)

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

넷째 줄에 M개의 양의 정수 B1,B2,⋯,BM이 주어집니다. (1≤Bi≤100)

출력

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

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

---

풀이

두 수열에 대해 구할 수 있는 모든 공통 부분 수열에 대해, 문제에서 제시한 조건에 부합하는 사전 순으로 나중인 공통 부분 수열을 구하는 문제다.

문제에서 제시한 조건에 부합하는 공통 부분 수열은 결국 내림차순으로 정렬된 부분 수열이다.

따라서, 두 수열의 모든 수를 비교해가며 내림차순으로 정렬된 부분 수열을 구하면 된다.

입력을 받은 후

두 수열의 최대값과 최대값의 인덱스를 구해주자.

만약 두 수열의 최대값이 일치하지 않다면, 대소비교에 따라 찾은 최대값을 삭제 후 다시 탐색하자.

만약 두 수열의 최대값이 일치한다면, 결과 리스트에 담아주자. 

그리고 다음 탐색 대상은 최대값이 위치한 다음 인덱스부터 탐색을 진행하면 된다.

두 수열에 대해 내림차순으로 만들어지는 공통 부분 수열의 수에 대해 이전 범위는 탐색 대상이 아니기 때문이다.

또한, 두 수열의 길이는 각각 100으로 O(N^2)으로 풀이가 가능하다.

결과 리스트의 길이와, 요소들을 출력하면 된다.

---

소스코드

보기

---

출처

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