백준 30805: 사전 순 최대 공통 부분 수열(Python/파이썬)

사전 순으로 가장 늦게 오는 부분 수열을 찾는 문제.
처음엔 두 수열을 뒤부터 돌면서 공통 값이 있고, prev보다 크면 res에 넣는 방식을 썼는데 이런 저런 오류가 많이 났다..
비내림차순이 사전 순 최대 값을 보장하지 못하는 문제 등

풀이

1. 두 수열의 최댓값을 비교한다.
2. 최댓값이 같다면
   2.1. 결과 배열 res에 최댓값을 추가한다
   2.2. 최댓값 다음 인덱스부터 시작하는 부분 수열에 대해 1.부터 반복한다.
3. 최댓값이 다르다면
   3.1. 둘 중 더 큰 최댓값을 배열에서 제거한다.
   3.2. 수정된 수열에 대해 1.부터 반복한다

이런 방식으로 두 수열 중 하나가 빈 배열이 되어 더 이상 비교할 값이 없을 때까지 최댓값 비교를 수행한다.

코드

import sys
input = sys.stdin.readline

def find_max(arr1, arr2):
    if not arr1 or not arr2:
        return

    tar1, tar2 = max(arr1), max(arr2)
    idx1, idx2 = arr1.index(tar1), arr2.index(tar2)

    if tar1 == tar2:
        res.append(tar1)
        find_max(arr1[idx1+1:], arr2[idx2+1:])

    elif tar1 > tar2:
        arr1.pop(idx1)
        find_max(arr1, arr2)

    else:
        arr2.pop(idx2)
        find_max(arr1, arr2)


n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
res = []

find_max(a, b)

print(len(res))
print(*res)

n과 m이 둘 다 <= 100이라 최대 200번 재귀 호출 후 종료.

max()와 index(n), pop(n) 모두 0번 인덱스부터 탐색하며 값을 찾기 때문에 각 O(n)의 시간복잡도를 갖는다.

최악의 경우 (n+m)번의 재귀 호출 발생하므로 시간 복잡도는 O((n+m)^2)이 된다.