문제

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

입력설명

첫 번째 줄에 첫 번째 리스트의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 리스트의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 리스트 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

출력설명

오름차순으로 정렬된 리스트를 출력합니다.

입력예제 1

3
1 3 5
5
2 3 6 7 9

출력예제 1

1 2 3 3 5 6 7 9

풀이

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

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))

sumArr = a+b
sumArr.sort()
print(sumArr) 

=> a,b리스트는 이미 정렬이 된 상태로 입력이 되기 때문에 상단과 같이 단순히 리스트를 합친 상태에서 다시 sort를 돌리는 것은 시간복잡도상 좋지 않은 방법!

풀이2

# 포인터
p1=p2=0

# 결과 리스트
c=[]

# 둘중의 하나의 포인터가 끝날때 까지
# =>하나의 포인터가 끝나면 남은 포인터의 배열 요소는 이미sort가 된 상태기 때문에
# 그대로 결과 리스트에 append하면 되기 때문
while p1<n and p2<m:
    if a[p1]<=b[p2]:
        c.append(a[p1])
        p1 += 1
    else:
        c.append(b[p2])
        p2 += 1
        
#while문이 종료된 후 종료되지 않은 포인터 분기처리 후 해당포인터 뒤의 리스트 요소를
#결과값 배열에 append
if p1<n:
    arr = a[p1:len(a)]
    c.extend(arr)
else:
    arr = b[p2:len(b)]
    c.extend(arr)

for i in c:
    print(i, end=" ")