Baekjoon 30805. 사전 순 최대 공통 부분 순열 / Python

문제 요약

두 수열 AAA와 BBB가 주어졌을 때, 이 두 수열의 공통 부분 수열 중 사전 순으로 가장 나중에 오는 수열을 구하는 문제다. 부분 수열이란 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장하는 것을 의미한다. 사전 순으로 나중이라는 것은 첫 번째 수가 큰 쪽을 의미하고, 첫 번째 수가 같다면 두 번째 수로 비교를 이어가는 것을 의미한다.

알고리즘 설명

알고리즘 개요

1. 최대 공통 부분 수열 찾기: 두 수열에서 공통으로 등장하는 가장 큰 값을 찾아 나감.
2. 재귀적 접근: 가장 큰 값을 찾으면 그 값을 결과에 추가하고, 그 이후의 부분 수열에 대해 다시 같은 작업을 반복한다.
3. 탐색 및 제거: 각 단계마다 가장 큰 값을 찾고, 해당 값을 제거하면서 다음 단계로 넘어감.
4. 종료 조건: 어느 한 수열이 빈 리스트가 되면 종료.

시간복잡도

• 시간복잡도 O(N ^ 2)
• 두 수열의 길이가 최대 100이므로 최악의 경우 최대 100 * 100 = 10,000번의 비교를 수행할 수 있다. 이는 충분히 실행 가능하다.

코드 설명

1. 입력 처리: 두 수열의 길이와 값을 입력받아 각각 arr1과 arr2에 저장한다.
2. 최대값 탐색: sol 함수에서 각 단계마다 두 수열에서 최대값을 찾아 비교한다.
3. 재귀 호출: 최대값이 동일한 경우 그 값을 결과 리스트 res에 추가하고, 그 이후의 부분 수열에 대해 재귀 호출한다. 최대값이 다르면 큰 값을 가진 수열에서 그 값을 제거하고 다시 재귀 호출한다.
4. 결과 출력: 최종적으로 구해진 공통 부분 수열의 길이와 값을 출력한다.

def sol(arr1, arr2, res = []):
    
    # 두 배열 중 하나라도 비어 있으면 결과 반환
    if (not arr1) or (not arr2):
        return res
    
    # arr1과 arr2에서 각각 가장 큰 값과 그 인덱스를 찾음
    tmp1, tmp2 = max(arr1), max(arr2)
    idx1, idx2 = arr1.index(tmp1), arr2.index(tmp2)

    # 두 값이 같으면 결과에 추가하고 그 이후 부분으로 재귀 호출
    if tmp1 == tmp2:
        res.append(tmp1)
        return sol(arr1[idx1 + 1:], arr2[idx2 + 1:], res)
    # tmp1이 더 크면 arr1에서 제거하고 재귀 호출
    elif tmp1 > tmp2:
        arr1.pop(idx1)
        return sol(arr1, arr2, res)
    # tmp2가 더 크면 arr2에서 제거하고 재귀 호출
    else:
        arr2.pop(idx2)
        return sol(arr1, arr2, res)


n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

# 함수 호출
ans = sol(arr1, arr2)

# 결과 출력
print(len(ans))
if ans:
    print(*ans)