[백준/Python] 배열 합치기_11728

알고리즘 분류 : 정렬, 투포인터

시간 복잡도 : 정렬 - O(NlogN), 투포인터 - . 

 

Try_1) Success

• 정렬 함수를 사용하여 접근했다

Try_2) Success

• 투 포인터를 사용하여 접근했다

'''
Condition
    - TL : 1.5s (약 3000만)
    - ML : 256mb (약 64*10만)
    - 1<=N,M<=100만
    - 두 배열은 정렬된 상태이다

Qustion
    - 두 배열을 합친 후, 정렬한 결과는?

Access
    - 두 배열을 합치고 sort 함수를 사용
    - 혹은, 투포인터를 사용하여 두 배열의 값을 앞에서부터 차례대로 비교(정렬된 배열이므로 가능)
'''


from sys import stdin
input = stdin.readline

#input data
n,m = map(int,input().split())
arr_a = list(map(int,input().split()))
arr_b = list(map(int,input().split()))

"""정렬"""
arr = sorted(arr_a + arr_b)
print(*arr, sep=' ')
    
"""투포인터"""
p_a=0
p_b=0
while p_a<n or p_b<m:
    if p_a == n:
        print(*arr_b[p_b:], sep=' ')
        break
    elif p_b == m:
        print(*arr_a[p_a:], sep=' ')
        break

    if arr_a[p_a] > arr_b[p_b]:
        print(arr_b[p_b], end=' ')
        p_b +=1
    else:
        print(arr_a[p_a], end=' ')
        p_a +=1

효율 : 정렬(1532ms) > 투포인터(2304ms)