투 포인터 알고리즘 응용문제 배우기2 -정렬된 두 리스트의 합집합-

1. 개요

 

이미 정렬되어 있는 2개의 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하라한다면 어떻게 해야할까

 

 

2. 알고리즘

 

2-1) 정렬된 리스트 A와 B를 입력받는다

 

2-2) 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리킨다

 

2-3) 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리킨다

 

2-4) A[i]와 B[j]중 더 작은 원소를 결과 리스트에 담는다

 

만약 A[i]가 더 작다면 i를 1 증가시킨다

 

B[j]가 더 작다면 j를 1 증가시킨다

 

2-5) 만약 i나 j가 가리키는 리스트의 길이를 넘어서는 경우, 남아있는 리스트의 원소를 모두 차례대로 담으면 된다

 

병합정렬이랑 똑같잖아?

 

 

3. 예시를 통해 이해하는 알고리즘

 

A = [1,3,5]이고 B=[2,4,6,8]일때, 두 리스트의 정렬된 합집합을 구해보자

 

 

먼저 두 리스트의 모든 원소가 들어갈 수 있는 초기 리스트를 생성하고, i가 리스트 A의 0번째 원소

 

j가 리스트 B의 0번째 원소를 가리키도록 만든다

 

i와 j가 가리키고 있는 원소의 크기를 비교하여 더 작은 원소를 결과 리스트에 담는다

 

담긴 원소의 번호를 1 증가시킨다

 

i가 가리키는 1이 더 작으므로 1을 담고 i를 1 증가시킨다

 

 

 

다시 i가 가리키는 원소와 j가 가리키는 원소를 비교하고, j가 가리키는 원소가 더 작으므로 2를 담고

 

j를 1 증가시킨다

 

 

 

이번에는 i가 가리키는 원소가 더 작으므로 3을 담고, i를 1 증가시킨다

 

 

 

이번에는 j가 가리키는 원소가 더 작으니 4를 담고 j를 1 증가시킨다

 

 

이번에는 i가 가리키는 원소가 더 작으니 5를 담고 i를 1 증가시킨다.

 

이제 i는 리스트 크기를 벗어났으니 더는 고려할 필요가 없다

 

 

 

이제 i가 리스트의 길이를 벗어났으니, 남아있는 j가 가리키는 원소를 차례대로 담으면 되겠다

 

 

4. 구현 예시

 

각 리스트의 길이가 N,M이라면 시간복잡도는 O(N+M)이다. 각 리스트의 모든 원소를 한번씩만 순회하면 되기 때문이다

 

i < n 이거나 j < m일때 반복문을 계속 수행한다

 

j >= m이면 B가 전부 처리되었고, i < n이고 A[i] <= B[j]이면, A의 원소가 더 적다는 뜻이고

 

이럴때 A의 원소를 result에 넣어준다

 

그렇지 않으면 A가 전부 처리되었거나, B의 원소가 더 적다는 뜻으로 B의 원소를 result에 넣어준다

 

어느 경우에나 원소를 넣어주므로 넣어주는 위치는 매 반복마다 k += 1 증가

 

#사전에 정렬된 리스트 A,B 선언

n,m = 3,4

A = [1,3,5]
B = [2,4,6,8]

#리스트 A,B의 모든 원소를 담을 수 있는 크기의 결과 리스트

result = [0]*(n+m)

i = 0
j = 0
k = 0

#모든 원소가 담길때까지 반복

while i < n or j < m:
    
    #리스트 B의 모든 원소가 처리되었거나
    #리스트 A의 원소가 더 작다면..
    if j >= m or (i < n and A[i] <= B[j]):
        
        result[k] = A[i] #더 작은 A의 원소를 넣고
        i += 1 #i를 1 증가시킨다
    
    else: #리스트 A의 원소가 모두 처리되었거나, B의 원소가 더 작다면...

        result[k] = B[j] #더 작은 B의 원소를 넣고
        j += 1 #j를 1 증가시킨다
    
    k += 1#원소를 하나 넣었으므로 다음에 넣을 위치

for num in result:
    
    print(num,end=' ')
"""
1 2 3 4 5 6 8 
"""