Algorithm - 두 리스트 합치기

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[두 리스트 합치기]

 

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

 

 

*입력 설명

첫 번째 줄에 첫 번째 리스트의 크기 N(1 ≤ N ≤ 100)이 주어진다.

두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어진다.

세 번째 줄에 두 번째 리스트의 크기 M(1 ≤ M ≤ 100)이 주어진다.

네 번째 줄에 M개의 리스트 원소가 오름차순으로 주어진다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않는다.

 

*출력 설명

오름차순으로 정렬된 리스트를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_14.txt', 'rt')

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:]
if p2 < m:
    c = c + b[p2:]

for x in c:
    print(x, end=' ')
    
# 출력 : 1 2 3 3 5 6 7 9

 

input_14.txt(입력)

3
1 3 5
5
2 3 6 7 9

 

 

중요내용

1. 두 리스트를 연산한 후, sort() 함수를 사용해서 원하는 결과를 출력할 수도 있다. 이처럼 sort() 함수를 사용하면, 두 리스트의 데이터를 n * log(n)번의 데이터를 비교하여 결과를 도출(정렬)한다.
2. 반면, 반복문(while문)을 사용하면 두 리스트의 데이터를 n번만 비교하여 결과를 도출(정렬)할 수 있다. 이러한 차이는 데이터가 많을수록 커지며, 반복문으로 위의 문제를 접근하길 권한다.
3. 참고로, 위의 답안에서 p1과 p2는 포인트 변수이며 두 변수 중 하나가 n과 m보다 같거나 커지게 되면, 이에 해당하는 리스트의 나머지 데이터를 슬라이싱 기능을 통해 리스트 c에 넣는 것이다.