두 리스트 합치기

인프런 김태원 강사님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Uiep

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

 

문제

나는 이 문제를 정말 단순한 문제로 생각했다.

#내 풀이
n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

arr3 = arr1 + arr2
arr3.sort()
for i in arr3:
    print(i, end = ' ')

그냥 각각 리스트로 받아서
합친후에, 파이썬 내장함수 sort를 사용하여 풀었는데

답은 맞았지만, 강사님이 이렇게 푸는거 말고 다른 방식을 생각하라고 하였다.

 

파이썬의 내장함수 sort는 병합정렬과 삽입정렬을 섞은 Tim 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:]
else:
    c = c + b[p2:]

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

이 방식은 포인터 두개를 이용하여

리스트의 값을 하나하나 비교해가면서 더 작은 리스트를

새로운 리스트에 append 해주는 방식이다.

 

이렇게 하면 500개 500개의 정렬된 리스트 두개를 합칠 때

1번 방식의 시간복잡도는 O(1000log(1000)),
2번 방식의 시간복잡도는 O(1000) 으로 시간을 단축할 수 있다.

 

코딩테스트는 조건이 까다로울테니 이러한 다른 방식도 익혀놔야겠다고 생각했다.