두 리스트 합치기

두 리스트 합치기

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

---

▣ 입력설명

첫 번째 줄에 첫 번째 리스트의 크기 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())
nlist = list(map(int,(input().split())))
m = int(input())
mlist = list(map(int,(input().split())))
ans = nlist + mlist
ans.sort()
print(ans, end=' ')

파이썬의 sort()는 퀵정렬이며 시간복잡도는 O(n logn) 이다.

이미 정렬되어 있다는 사실을 이용하면 8번만 반복되기만 하면 O(n) 으로 끝낼 수 있다.

 

 

n = int(input())
nlist = list(map(int,(input().split())))
m = int(input())
mlist = list(map(int,(input().split())))
ans = []
# 같거나 작으면 n 추가, else m추가
p1, p2 = 0, 0
while (True):
    if nlist[p1] <= mlist[p2]:
        ans.append(nlist[p1])
        p1 += 1
        if p1==n:
            break
    elif nlist[p1] > mlist[p2]:
        ans.append(mlist[p2])
        p2 += 1
        if p2==n:
            break

if p1==n: # nlist가 먼저 끝났다면
    for i in range(p2, m):
        ans.append(mlist[i])
elif p2==m: # mlist가 먼저 끝났다면
    for i in range(p1, n):
        ans.append(nlist[i])

''' 위와 같은 방식
if p1==n:
    ans = ans + mlist[p1:]
elif p2==m:
    ans = ans + nlist[p2:]
'''

for x in ans: # 리스트를 옆으로 출력
    print(x, end=' ')

리스트의 인덱스 끼리 비교해서 O(n) 으로 끝낼 수 있다.