파이썬 알고리즘-14 (탐색)두 리스트 합치기

14.두 리스트 합치기
오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로그램을 작성하세요. (sort() 사용 금지)

▣ 입력설명
첫 번째 줄에 첫 번째 리스트의 크기 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

내 코드

n=int(input())
lst1=list(map(int, input().split()))
m=int(input())
lst2=list(map(int, input().split()))

new_list=lst1+lst2
new_list.sort()
for i in new_list:
    print(i, end=' ')

답은 맞는데 문제 취지와는 맞지 않았다. sort함수를 사용하게 되면 정렬하는데 걸리는 시간복잡도가 O(nlogn)인 반면, 이미 정렬되어 있다는 것을 이용한 풀이와 같은 방법은 O(n)이므로 이 중에서 더 효율적인 방법을 써야 한다.

풀이

n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int, input().split()))
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=' ')

반성점

• while문의 범위 설정하는 것이 아직 익숙하지 않은 것 같다. 코드를 제대로 이해하지 못해서 더 그런 것 같다.

배운 것

• 두 리스트를 더해 정렬해야 할 경우에는 포인터(여기서는 리스트의 인덱스를 포인터처럼 사용)를 활용해 비교한 후 새 리스트에 작은 값을 먼저 append하고 그 포인터 값을 +1 해준다.