정렬되어 있는 두 개의 리스트 A와 B가 있다고 가정해 보겠습니다. 이 두 리스트를 병합하여 하나의 정렬된 리스트 C를 만들어야 하며, 두 리스트의 크기는 서로 달라도 괜찮습니다.
예를 들어 A = [1,2,4,7], B = [1,3,4,5,6,8]이라면, 병합된 리스트 C는 [1,1,2,3,4,4,5,6,7,8]이 됩니다.
병합 알고리즘의 동작 원리
이 문제는 투 포인터(Two Pointer) 기법을 활용해 효율적으로 해결할 수 있습니다. 각 리스트의 첫 번째 요소부터 값을 하나씩 비교하면서, 더 작은 값을 결과 리스트에 순서대로 추가하는 방식입니다. 구체적인 동작 과정은 다음과 같습니다.
- 결과를 담을 새로운 빈 리스트 x를 생성합니다.
- 포인터 i := 0, j := 0으로 초기화합니다.
- i가 lst0의 길이보다 작고, j가 lst1의 길이보다 작은 동안 반복합니다.
- lst0[i] > lst1[j]인 경우: lst1[j]를 x의 끝에 추가하고 j를 1 증가시킵니다.
- lst0[i] < lst1[j]인 경우: lst0[i]를 x의 끝에 추가하고 i를 1 증가시킵니다.
- 두 값이 같은 경우: 두 요소를 모두 x에 추가한 뒤 i와 j를 각각 1씩 증가시킵니다.
- lst0에 아직 남은 요소가 있다면 모두 x의 끝에 추가합니다.
- lst1에 아직 남은 요소가 있다면 모두 x의 끝에 추가합니다.
- 완성된 리스트 x를 반환합니다.
Python 구현 예제
위 알고리즘을 실제 코드로 구현하면 다음과 같습니다.
class Solution:
def solve(self, lst0, lst1):
x = []
i = 0
j = 0
while(i < len(lst0) and j < len(lst1)):
if(lst0[i] > lst1[j]):
x.append(lst1[j])
j = j + 1
elif(lst0[i] < lst1[j]):
x.append(lst0[i])
i = i + 1
else:
x.append(lst0[i])
x.append(lst1[j])
i = i + 1
j = j + 1
while(i < len(lst0)):
x.append(lst0[i])
i = i + 1
while(j < len(lst1)):
x.append(lst1[j])
j = j + 1
return x
ob = Solution()
print(ob.solve([1,2,4,7], [1,3,4,5,6,8]))
입력
[1,2,4,7], [1,3,4,5,6,8]
출력
[1, 1, 2, 3, 4, 4, 5, 6, 7, 8]
시간 및 공간 복잡도
이 알고리즘은 두 리스트의 모든 요소를 정확히 한 번씩만 확인하므로, 시간 복잡도는 O(n + m)입니다(n, m은 각 리스트의 길이). 단순히 두 리스트를 합친 뒤 정렬하는 sorted(A + B) 방식(O((n+m) log(n+m)))보다 효율적입니다. 공간 복잡도는 결과 리스트를 저장해야 하므로 마찬가지로 O(n + m)입니다.
참고: 표준 라이브러리 활용
직접 구현하지 않고 Python 표준 라이브러리를 사용할 수도 있습니다. heapq.merge()는 정렬된 여러 입력을 병합하는 이터레이터를 반환하며, 내부적으로 동일한 원리로 동작합니다.
from heapq import merge
print(list(merge([1,2,4,7], [1,3,4,5,6,8])))
# [1, 1, 2, 3, 4, 4, 5, 6, 7, 8]