[Algorithms] Basic-두 리스트 합치기

 

• 파이썬의 sort()를 쓰면 쉽겠지만, sort 함수는 nlogn의 시간 복잡도를 가진다
• 시간 복잡도가 n이 되는 더 효과적인 방법이 있다. 각 리스트가 오름차순으로 정렬 되어있다는 사실을 기반으로 포인터를 사용해서 해결한다. 

 

 

import sys
 
sys.stdin = open("input", "rt")
a_n = int(input())
a = list(map(int, input().split()))
b_n = int(input())
b = list(map(int, input().split()))
 
c = []
a_ptr, b_ptr = 0, 0                    // 각 리스트의 포인터
 
while a_ptr < a_n and b_ptr < b_n:    // 하나의 리스트라도 포인터가 끝에 도달하면 break
    if a[a_ptr] <= b[b_ptr]:
        c.append(a[a_ptr])
        a_ptr += 1
    else:
        c.append(b[b_ptr])
        b_ptr += 1
 
if a_ptr < a_n:                        // 옮기지 못한 수들에 대하여 마저 옮긴다
    c = c + a[a_ptr:]
if b_ptr < b_n:
    c = c + b[b_ptr:]
 
for i in c:
    print(i, end=" ")