[백준 BOJ / Python] 30805번 사전 순 최대 공통 부분 수열

문제

두 수열이 주어졌을 때 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하는 문제이다. 

여기서 부분 수열이란 것은 어떤 수열에서 원래 순서를 유지하면서 일부 원소를 선택하여 만들어진 새로운 수열을 말한다.

풀이

1. A, B 두 개의 수열이 주어졌을 때 공통되는 부분 수열을 구해야 한다. 따라서 set을 사용하여 A와 B 수열의 공통되는 숫자를 선별한다.
2. 만약 공통되는 숫자가 없다면 0을 출력하고 종료하면 된다.
3. 부분 수열들 중 사전 순으로 가장 나중인 것을 구하는 것이기 때문에, 공통 숫자들 중 가장 큰 숫자(max_val)를 뽑아 result에 담는다.
4. 부분 수열은 원래 수열의 순서를 유지하면서 선택돼야 하므로, A와 B 각각의 수열에서 max_val의 위치를 찾아 해당 위치 이후의 수열로 업데이트한다.
5. 다시 두 수열의 공통되는 숫자들을 구하고 3번과 4번 과정을 반복한다.

Python 코드

import sys
input = sys.stdin.readline

# 입력 받기
n = int(input())
arrA = list(map(int, input().split()))
m = int(input())
arrB = list(map(int, input().split()))

# 두 수열의 공통되는 숫자 집합 구하기
common_elements = set(arrA) & set(arrB)

# 공통되는 숫자가 없으면 0 출력 후 종료
if not common_elements:
    print(0)
    exit()

result = []
while common_elements:
    # 공통 숫자들 중 최대값 찾기
    max_val = max(common_elements)
    result.append(max_val)

    # 각각의 A와 B 수열에서 최대값 이후의 부분 수열로 업데이트
    idx1 = arrA.index(max_val)
    idx2 = arrB.index(max_val)
    arrA = arrA[idx1 + 1:]
    arrB = arrB[idx2 + 1:]

    # 새로운 공통 숫자 집합 구하기
    common_elements = set(arrA) & set(arrB)

# 결과 출력
print(len(result))
print(*result)

 

문제출처

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