정렬된 두 리스트 합치기 (sort 함수, 투 포인터)

문제

오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력
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=" ")