배열 합치기 백준 11728번 정렬

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

문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

간단하게 두 배열이 있고 합치는건데

n,m = map(int,input().split())
list_a = list(map(int,input().split()))
list_b = list(map(int,input().split()))
print(*sorted(list_a+list_b))

이러면 파이썬으로도 통과!는 되지만…. 코드를 한번 짜봐야 겠지요 그렇게 어렵지는 않습니다.

어렵지 않은 이유는 조건에서 주어지는 두 배열이 “정렬된 것”으로 주어지기 때문입니다.

그러면 맨 앞에거만 보면서 작은리스트를 하나 만들면됩니다.

n,m = map(int,input().split())
list_a = list(map(int,input().split()))
list_b = list(map(int,input().split()))
list_c = []

aidx = 0
bidx = 0
for i in range(n+m):
    if bidx == m:
        list_c.append(list_a[aidx])
        aidx+=1
    elif aidx == n:
        list_c.append(list_b[bidx])
        bidx+=1
    elif list_a[aidx]<=list_b[bidx]:
        list_c.append(list_a[aidx])
        aidx+=1
    else:
        list_c.append(list_b[bidx])
        bidx+=1
        
print(*list_c)

입력을 받을 두개의 리스트와 하나의 정답을 답을 리스트를 준비합시다. 그리고 쭉 보면 됩니다.

만약 어느 하나가 끝까지 도달하면 다른 리스트를 쭉 채우면 됩니다. 또는 두 리스트를 비교했을때 어느 하나가 작다면 작은 것을 먼저 정답리스트에 채워나가면 됩니다. 우리는 두개의 커서 aidx, bidx를 가지고 쭉 비교하면 됩니다.

파이썬에서 sort함수를 사용할경우 O(nlogn)임을 기역하면 두번째 방법은 O(n)으로 끝낼 수 있으니 훨씩 시간도 빠른 것을 결과를 보기전에도 알 수 있습니다.

라고 생각했는데 sort함수 쓴게 훨씬 빠르네요….?