백준 11728

정렬된 2개의 배열이 주어질 때,
두 배열을 합치고 정렬해서 원소 값을 출력하는 문제이다.

sorted()를 사용해도 풀 수 있다.

시간 제한에 걸리지 않기 때문이다.

각 배열의 최대 크기는 10^6개이므로,
두 배열의 합친 배열의 최대 크기는 2*(10^6)개이다.

그리고 sorted()의 시간 복잡도는 O(NlogN)이므로,
총 연산 횟수는 2(10^6)log(2(10^6))이다.

2(10^6)log(2(10^6)) = 2(10^6) (log2 + log(10^6))

2(10^6)이 약 20이므로,
약 4 10^7회의 연산이다.

보통 1GHz가 1초에 10^9회의 연산을 수행할 수 있다는 것을 의미하므로,
이는 1초 내에 끝난다고 볼 수 있다.

코드(정답)은 다음과 같다.

# 11728

import sys

'''
1) "정렬되어 있는" 2개의 배열이 주어진다.
2) 두 배열을 합친다.
3) 합쳐진 배열을 오름차순으로 정렬한다.
4) 배열의 원소를 띄어쓰기로 구분하여 출력한다.
'''

n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

nums = sorted(a + b)
for num in nums:
    print(num, end=' ')

여기서 결과를 출력하는 다른 방법도 있다.

# 방법1
nums = sorted(a + b)
print(*nums)

# 방법2
nums = sorted(a + b)
print(' '.join(map(str, nums)))

그런데 이 문제는 정렬된 두 배열이 주어지고,
두 배열을 합친 배열의 정렬된 값을 출력하는 문제이므로,
'투 포인터'라는 알고리즘으로 접근할 수도 있다.