728x90
문제
오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력
3
1 3 5
5
2 3 6 7 9
1 2 3 3 5 6 7 9
분석
sort()의 시간복잡도 : nlogn ➔ 정렬된 두 리스트 합치기 시간복잡도 : n
풀이
# 시간복잡도 n
n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))
c=[] # 정답 리스트
p1=p2=0
while p1<n and p2<m:
# 투포인터 작은값을 c에 넣어서 정렬
if a[p1]<b[p2]:
c.append(a[p1])
p1+=1
else:
c.append(b[p2])
p2+=1
# 끝까지 못가고 남음
if p1<n:
c=c+a[p1:]
if p2<m:
c=c+b[p2:]
for i in c:
print(i, end=" ")
# 시간복잡도 8log8
n=int(input())
nlist=list(map(int,input().split()))
m=int(input())
mlist=list(map(int,input().split()))
a=nlist+mlist
a.sort()
for i in range(len(a)):
print(a[i], end=" ")
728x90