테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 배열 합치기 ======

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


===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_5}}