백준 11728 : 배열 합치기 (Python)

본문 링크

투 포인터

N,M=map(int,input().split())

A=list(map(int,input().split()))
B=list(map(int,input().split()))

ans=[]

a=0
b=0
while a!=len(A) or b!=len(B):

    if a == len(A):
        ans.append(B[b])
        b+=1
    elif b == len(B):
        ans.append(A[a])
        a+=1
    else:
        if A[a]<B[b]:
            ans.append(A[a])
            a+=1
        else:
            ans.append(B[b])
            b+=1


print(*ans)

힙 정렬

import sys
input=sys.stdin.readline
import heapq
from heapq import heapify
N,M=map(int,input().split())

L=list(map(int,input().split()))
heapify(L)

L_2=list(map(int,input().split()))

for i in range(M):
    heapq.heappush(L , L_2[i])

for i in range(N+M):
    print(heapq.heappop(L) , end=" ")

📌 어떻게 문제에 접근할 것인가?

문제는 간단하게 두 배열을 합한후 정렬하는 것이다.

하지만 범위가 $1 ≤ N, M ≤ 1,000,000$ 이므로 그냥 sort 를 해버리면 시간초과가 나버린다.
따라서 투포인터와 힙 정렬을 사용하였다.

먼저 투 포인터에서는 a=b=0 으로 잡아준후 A[a] 와 B[b] 값을 비교해서 더 작은값을 ans 배열에 넣어준다. 그리고 넣어준 값은 인덱스를 증가시킴으로써
ans 배열은 자동적으로 오름차순 정렬이 된다.

다음으로 힙 정렬은 L 리스트를 입력받고 heapify 를 사용해여 리스트를 힙으로 변환시킨다.
다음으로 L_2 의 리스트값을 heappush 해준후 마지막에 heappop 으로 출력해준다.

✅코드에서 주의해야 할 점

• 투 포인터에서 가능하면 elif 문을 사용하지말고 else 문을 사용하자. 연산속도가 조금 더 빨라진다.