1 minute read

문제

접근 방법

문제 제목 때문에 DP를 써야하는가 생각을 잠깐 했지만 계속해서 공통이면서 사전순으로 나중인 부분 수열을 얻어내면 답은 결국 얻어낼 수 있다는 것을 파악했다. 그래서 Greedy하게 접근하기로 했다.

각 배열에 index를 하나씩 움직이면서 공통이면서 사전순으로 맨 뒤인 character를 찾는 과정을 반복했다. 찾는 과정이 다른 과정에 영향을 주지 않고 이를 반복하면 사전순으로 가장 나중인 부분 수열을 얻을 수 있기 때문에 Greedy algorithm를 쓰는 것이 맞았다.

n <= 100이기 때문에 $O(n^2)$을 최대 n번 반복해도 $100^3$이기 때문에 시간복잡도를 충분히 만족했다.

정답 코드


import sys
input = sys.stdin.readline

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

ans = 0

"""

a와 b에서 공통으로 나타나면서 사전순으로 제일 뒤인 지점을 찾는다. 

그 지점부터 다시 공통으로 나타나면서 사전순으로 제일 뒤인 지점을 찾는다.

이 과정을 반복하면 될 거 같다.

"""
ans = []

def iterate(a_i, b_i):
    latest = 0
    a_index, b_index = 0,0
    for i in range(a_i, n):
        for j in range(b_i, m):
            if a[i] == b[j] and a[i] > latest:
                latest = a[i]
                a_index = i
                b_index = j
    if latest == 0:
        return 0,0,0
    return latest, a_index, b_index

a_i, b_i = 0,0
cnt = 0
while True:
    latest, a_i, b_i = iterate(a_i, b_i)
    a_i+=1
    b_i+=1
    if latest == 0:
        break
    ans.append(latest)
    cnt += 1

print(cnt)
for s in ans:
    print(s, end=' ')

You May Also Enjoy