[알고리즘] 두 리스트 합치기

📌

오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로 그램을 작성하세요.

 

< input example >

 

3 #길이

1 3 5 #value

5 #길이

2 3 6 7 9 #value

 

 

✔️ code

 

import sys
sys.stdin=open("input.txt", "r")

n=int(input())
list_n=list(map(int, input().split()))
m=int(input())
list_m=list(map(int, input().split()))

#list_m value를 list_n에 추가 
for i in list_m:
    list_n.append(i)

#정렬
list_n.sort()
print(list_n)

 

>>>

 

코드가 짧고 단순해서 좋아했는데 좋아할 것이 아니었다.

이렇게 sort() 메소드를 사용하면 nlogn 의 시간 복잡도가 사용되기 때문에,

다른 효율적 알고리즘을 이용해야 한다.

 

📍

p1과 p2는 각각 a,b 리스트 value 를 가르키는 포인터 역할을 한다.

a[p1] 과 b[p2] 를 비교해서 새로운 리스트 c 에 append 하고,

append 된 값을 가진 리스트의 포인터를 1 증가시켜주는 방식이다.

만약 a 리스트가 먼저 c 리스트에 정렬되면 b의 남은 값은 c 리스트 뒤에 더해주는 방식을 사용했다.

 

 

#sort() 시간 복잡도: nlogn
p1=p2=0
c=[]
while p1<n and p2<m:
    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 x in c:
    print(x, end=' ')