[Python] 11728번 배열 합치기

https://www.acmicpc.net/problem/11728

---

 

24/11/25

 

 

단순히 배열 두 개를 합쳐서 정렬하는 문제다.

---

 

문제 접근 방식:

 

 

파이썬에서 그냥 나이브하게 합쳐서 정렬하면 된다. 근데, 그러면 너무 재미 없으니까, 두 포인터로 푸는 방법도 알아보자.

 

이미 정렬된 상태로 주므로, 배열 A와 배열 B를 가리키는 포인터 두 개($i$와 $j$)를 선언하고, $A[i] < B[j]$인 경우 정답 배열에 $A[i]$를 담고, 그렇지 않은 경우 $B[j]$를 담도록 한다.

 

시복도는 $\mathcal{O}(N+M)$이 된다.

 

반면, 두 리스트를 나이브하게 합치고 정렬하는 방법은 $\mathcal{O}(N+M \log(N+M))$의 시복도가 든다.

 

근데 실제로 실행해보면 두 리스트를 나이브하게 합치고 정렬하는 방법이 시간이 더 적게 소요가 되는데, 이는 정답 배열에 append를 하는 연산의 실행 속도가 더 느려서 그런 것으로 추측된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11728번 배열 합치기
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(*sorted(A+B))