[BOJ]11728. 배열합치기 (python)

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

11728번: 배열 합치기

 

문제

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

입력

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

 

 

풀이

효율적인 풀이인지는 모르겠다. 그러나 merge sort를 연습하자는 의미에서 merge sort로 풀었다.
어차피 A, B는 모두 정렬된 상태이므로, 이 점을 살려서 정렬하는 것이 가장 효율적이기도 하다!

 

A, B를 각각 a_index, b_index 두 개의 포인터를 이용하여
앞에서부터 (작은 값부터) 비교하며 더 작은 값을 넣고, 해당 리스트의 포인터를 +1 해주었다.
(merge sort와 동일)

 

코드

import sys
read = sys.stdin.readline

size_A, size_B = map(int, read().split())

list_A = list(map(int, read().split()))
list_B = list(map(int, read().split()))

a_index = 0
b_index = 0

answer = []

while a_index < len(list_A) and b_index < len(list_B):
    if list_A[a_index] <= list_B[b_index]:
        answer.append(list_A[a_index])
        a_index += 1
    else:
        answer.append(list_B[b_index])
        b_index += 1

while a_index < len(list_A):
    answer.append(list_A[a_index])
    a_index += 1

while b_index < len(list_B):
    answer.append(list_B[b_index])
    b_index += 1

print(*answer)