728x90
반응형
문제 바로가기
문제:
어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.
- 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
- 예를 들어, {1,1,5}는 {3,1―,4,1―,5―,9}의 부분 수열이지만, {1,5,1}의 부분 수열은 아닙니다.
또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.
- 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
- 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
- 길이가 0인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.
양의 정수로 이루어진 길이가 N인 수열 {A1,⋯,AN}이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 M인 수열 {B1,⋯,BM}이 주어집니다.
수열 A와 수열 B가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.
입력:
첫 줄에 수열 A의 길이 N이 주어집니다. (1≤N≤100)
둘째 줄에 N개의 양의 정수 A1,A2,⋯,AN이 주어집니다. (1≤Ai≤100)
셋째 줄에 수열 B의 길이 M이 주어집니다. (1≤M≤100)
넷째 줄에 M개의 양의 정수 B1,B2,⋯,BM이 주어집니다. (1≤Bi≤100)
출력:
A와 B의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 K를 출력하세요.
K≠0이라면, 다음 줄에 K개의 수를 공백으로 구분해 출력하세요. i번째 수는 A와 B의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 i번째 수입니다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
A = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(input())
B = list(map(int, sys.stdin.readline().rstrip().split()))
numbers = set(A) & set(B)
if not numbers:
print(0)
exit()
res = []
while numbers:
number = max(numbers)
res.append(number)
A_idx = A.index(number)
B_idx = B.index(number)
A = A[A_idx + 1:]
B = B[B_idx + 1:]
numbers = set(A) & set(B)
print(len(res))
print(*res)
정렬했을경우 가장 큰 수가 뒤에 나온 후 길이를 잰다.
그러면 두 리스트가 겹치는 가장 큰 수를 기준으로 뒤로 쭉쭉 찾아가면 된다.
반응형
댓글