백준 #30805 사전 순 최대 공통 부분 수열

문제 링크

[30805 사전 순 최대 공통 부분 수열]

문제 설명

LCS(Longest Common Subsequence)랑 비슷해보이지만 다른 문제이다. 두 수열이 있고 각 수열에서 뽑은 공통 부분 수열중 사전 순으로 가장 나중을 찾는 문제

코드

import sys
input = sys.stdin.readline
from heapq import heappush, heappop


N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
hq_a = []
hq_b = []
for i in range(N):
    heappush(hq_a, (-A[i], i))
for i in range(M):
    heappush(hq_b, (-B[i], i))

result = [[0, -1, -1]]
a, a_idx = heappop(hq_a)
b, b_idx = heappop(hq_b)
a, b = -a, -b
while True:
    if a == b:
        result.append((a, a_idx, b_idx))
        if not hq_a or not hq_b:
            break
        while hq_a:
            temp, temp_idx = heappop(hq_a)
            if temp_idx > result[-1][1]:
                a = -temp
                a_idx = temp_idx
                break
        if temp_idx != a_idx:
            break
        while hq_b:
            temp, temp_idx = heappop(hq_b)
            if temp_idx > result[-1][2]:
                b = -temp
                b_idx = temp_idx
                break
        if temp_idx != b_idx:
            break
    elif a > b:
        if hq_a:
            while hq_a:
                temp, temp_idx = heappop(hq_a)
                if temp_idx > result[-1][1]:
                    a = -temp
                    a_idx = temp_idx
                    break
            if temp_idx != a_idx:
                break
        else:
            break
    elif a < b:
        if hq_b:
            while hq_b:
                temp, temp_idx = heappop(hq_b)
                if temp_idx > result[-1][2]:
                    b = -temp
                    b_idx = temp_idx
                    break
            if temp_idx != b_idx:
                break
        else:
            break

print(len(result) - 1)
for i in range(1, len(result)):
    print(result[i][0], end=" ")

풀이

우선순위 큐로 풀이했다. 어차피 사전 순으로 가장 마지막을 찾아야 하므로 최대힙을 사용했고 각 숫자의 순서도 고려해주어야 하기 때문에 각 숫자의 인덱스도 같이 저장해주었다.

두 수열에서 뽑은 숫자가 같다면 최종 리스트에 넣어주고 각 수열에서 현재 숫자의 이후 인덱스가 나올때 까지 pop을 해준다.

만약 A에서 뽑은게 더 크다면 A에서 pop해주면 되고 B 또한 마찬가지이다.

대회 문제인데 대회때 못풀었다. 뭔가 DP로 접근해야할것 같아서 계속 고민하다가 못풀었던 문제이다. 아직 많이 부족한듯!

아래는 대회 공식 해설인데 정말 깔끔하다.

def main():
    input()
    a = list(map(int, input().split()))
    input()
    b = list(map(int, input().split()))

    mx = max(max(a), max(b))
    ans = []
    for i in range(mx, 0, -1):
        while True:
            if i not in a or i not in b:
                break

            ans.append(i)
            a = a[a.index(i)+1:]
            b = b[b.index(i)+1:]

    print(len(ans))
    print(*ans, sep=' ')


if __name__ == "__main__":
    main()