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

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

주어진 두 수열의 공통 부분 수열 중 사전 순으로 가장 뒤에 있는 수열의 길이를 구하는 문제이다.

먼저 주어진 수열 중 공통이 아닌 부분을 지웠고, 그 이후 최댓값을 구해 각 수열에 해당 최댓값이 몇번 나오는지 구했다.

 

각 수열에서 최댓값이 나온 횟수 중 작은 값(min)만큼 부분 수열이 될 수 있으니 정답 문자열에 최댓값을 min번 붙여준 뒤,각 수열에서 해당 최댓값이 min번째 나오는 위치를 구해 해당 위치 기준으로 sublist한 뒤 동일한 처리를 반복해 list가 전부 비어있을 때 탈출하는 방법으로 풀었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        int count = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        List<Integer> a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
        br.readLine();
        List<Integer> b = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
        StringBuilder sb = new StringBuilder();
        while (!a.isEmpty() && !b.isEmpty()) {
            a = a.stream().filter(b::contains).collect(Collectors.toList());
            b = b.stream().filter(a::contains).collect(Collectors.toList());
            if (a.isEmpty()) break;
            int max = a.stream().mapToInt(Integer::intValue).max().getAsInt();
            int aCount = (int) a.stream().filter(i -> i == max).count();
            int bCount = (int) b.stream().filter(i -> i == max).count();
            int target = Math.min(aCount, bCount);
            for (int i = 0; i < target; i++) {
                sb.append(max);
                count++;
                sb.append(" ");
            }
            int aLast = getIdx(a,target,max);
            int bLast = getIdx(b,target,max);
            a = a.subList(aLast + 1, a.size());
            b = b.subList(bLast + 1, b.size());
        }
        System.out.println(count);
        if (count != 0) System.out.println(sb);
    }

    static int getIdx(List<Integer> a, int targetCount, int target) {
        int tidx = 0;
        int count = 0;
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i) == target) {
                count++;
                if(count==targetCount){
                    tidx = i;
                    break;
                }
            }
        }
        return tidx;
    }
}