배열 합치기

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	11728
문제명	배열 합치기
레벨	실버 5
분류	정렬
시간복잡도	O(n+m)
인풋사이즈	n<=1,000,000, m<=1,000,000
사용한 언어	Python
제출기록	306444KB / 840ms
최고기록	692ms
해결날짜	2021/09/16

풀이

두 정렬된 배열을 머지하라는 문제이다. 머지소트를 할때 반복적으로 수행하는 그 머지이다.
O(N+M)에 머지를 하는 정석적인 방법은 두 배열에서 각각 다음 숫자를 가리키는 포인터를 만들고, 숫자 두개를 비교해서 작은쪽을 결과에 추가하고 포인터를 증가시키는 방법이다. 이것도 일종의 투 포인터 알고리즘이라고 볼수 있긴 하고, 그래서 태그도 투 포인터가 붙어있긴 하다.
그냥 두 배열을 이어붙여서 소팅을 해도 된다. 특히 파이썬의 빌트인 소트 함수에서 사용되는 TimSort는 이러한 데이터는 O(n)에 처리한다. 그래서 그냥 내장 소트 함수를 쓰더라도 O¹⁾이 아니라 O(N+M)에 처리된다.
데이터의 갯수가 최대 2,000,000개로 상당히 많다. 소팅보다도 출력에 시간이 많이 걸리는데, 수 정렬하기 2에서 했던 것처럼 문자열의 리스트를 key=int 로 정렬한 다음에 문자열을 합쳐서 출력하는 것이, 정수 리스트를 정렬한 뒤 출력하는 것보다 빠르다.

코드

"""Solution code for "BOJ 11728. 배열 합치기".

- Problem link: https://www.acmicpc.net/problem/11728
- Solution link: http://www.teferi.net/ps/problems/boj/11728

Tags: [Sort]
"""


def main():
    N, M = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    A = input()
    B = input()
    print(' '.join(sorted(A.split() + B.split(), key=int)))


if __name__ == '__main__':
    main()

BOJ, 실버 5

¹⁾

N+M)log(N+M