문제 소개
사용자가 입력한 두 개의 리스트가 주어지며, 각 리스트의 요소들은 정렬되어 있지 않습니다. 이번 글에서는 이렇게 정렬되지 않은 두 배열을 하나로 병합한 후, 전체를 오름차순으로 정렬된 리스트로 만드는 Python 프로그램을 살펴보겠습니다.
예제
입력: A[] = {100, 50, 150}
B[] = {200, 30, 20}
출력: 병합 리스트: {20, 30, 50, 100, 150, 200}알고리즘
전체 절차는 다음과 같습니다.
- 먼저 두 개의 사용자 입력 리스트를 생성합니다.
- 최종 병합 리스트의 크기는 첫 번째 리스트의 크기와 두 번째 리스트의 크기를 합한 값입니다.
- sort() 메서드를 사용해 두 리스트를 각각 오름차순으로 정렬합니다.
- 정렬된 두 리스트를 비교하며 병합하여 세 번째 리스트에 저장합니다.
- a[]에 남은 요소가 있다면 이어서 병합하고, b[]에 남은 요소가 있다면 역시 병합합니다.
- 병합 후 정렬이 완료된 최종 리스트를 화면에 출력합니다.
예제 코드
# 정렬되지 않은 두 리스트를
# 정렬된 순서로 병합하는 Python 프로그램
# 배열을 정렬된 순서로 병합하는 함수
def unsortedarray(a, b, res, n, m):
# a[]와 b[]를 각각 정렬
a.sort()
b.sort()
# 정렬된 두 배열을 res[]로 병합
i, j, k = 0, 0, 0
while (i < n and j < m):
if (a[i] <= b[j]):
res[k] = a[i]
i += 1
k += 1
else:
res[k] = b[j]
j += 1
k += 1
while (i < n): # a[]의 남은 요소 병합(있다면)
res[k] = a[i]
i += 1
k += 1
while (j < m): # b[]의 남은 요소 병합(있다면)
res[k] = b[j]
j += 1
k += 1
# 드라이버 코드
A = list()
n = int(input("첫 번째 리스트의 크기 :: "))
print("첫 번째 리스트의 요소 입력 ::")
for i in range(n):
k = int(input(""))
A.append(k)
B = list()
m = int(input("두 번째 리스트의 크기 :: "))
print("두 번째 리스트의 요소 입력 ::")
for i in range(m):
k = int(input(""))
B.append(k)
# 최종 병합 리스트
res = [0 for i in range(n + m)]
unsortedarray(A, B, res, n, m)
print("정렬된 병합 리스트 :")
for i in range(n + m):
print(res[i])실행 결과
첫 번째 리스트의 크기 :: 4 첫 번째 리스트의 요소 입력 :: 8 79 56 3 두 번째 리스트의 크기 :: 4 두 번째 리스트의 요소 입력 :: 67 1 9 45 정렬된 병합 리스트 : 1 3 8 9 45 56 67 79
동작 원리
이 프로그램의 핵심은 투 포인터(Two Pointer) 기법입니다. 두 리스트를 각각 정렬한 뒤, 각 리스트의 맨 앞을 가리키는 포인터 i와 j를 두고 값을 서로 비교합니다. 더 작은 값을 결과 리스트에 넣고 해당 포인터를 한 칸 앞으로 이동시키는 과정을 반복하면, 두 리스트의 요소가 자연스럽게 오름차순으로 병합됩니다. 한쪽 리스트의 모든 요소를 처리했다면, 나머지 리스트에 남은 요소들은 이미 정렬된 상태이므로 그대로 이어 붙이기만 하면 됩니다.
시간 복잡도 측면에서 보면, 각 리스트를 정렬하는 데 O(n log n)과 O(m log m)이 걸리고 병합 단계는 O(n+m)의 선형 시간에 수행됩니다. 따라서 전체 시간 복잡도는 O((n+m)log(n+m))입니다.
마무리 팁
참고로 실무에서는 sorted(A + B) 한 줄만으로도 동일한 결과를 손쉽게 얻을 수 있습니다. 하지만 위 예제처럼 병합 과정을 직접 구현해 보면 정렬 알고리즘과 투 포인터 기법의 내부 동작 원리를 깊이 이해하는 데 큰 도움이 되므로, 학습 목적이라면 직접 코딩해 보는 것을 추천합니다.