[BOJ] 11728번: 배열 합치기

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


정렬되어있는 두 배열을 합쳐서 정렬되어있는 상태를 유지하는데에는 O(N+M)이 필요합니다. 이는 Merge sort를 할 때에도 필요한 알고리즘입니다.


예를 들어


1 2 4 7 8 10

3 6 11 16


- - - - - - - - - - -


을 합친다고 하면, 먼저 1과 3을 비교합니다. 이 때 작은 것을 취하고, 원래의 배열에서 지웁니다.(실제로 지우는 연산을 취하지는 않지만 관념적으로 지웠다고 합시다.)


x 2 4 7 8 10

3 6 11 16


1 - - - - - - - - - -


이제 2와 3을 비교합니다. 마찬가지로 2를 취하고, 원래의 배열에서 지웁니다.


x x 4 7 8 10

3 6 11 16


1 2 - - - - - - - - -


이제 4와 3을 비교합니다. 3을 취하고 원래의 배열에서 지웁니다.


x x 4 7 8 10

x 6 11 16


1 2 3 - - - - - - - -


이를 반복하면 한 번의 비교에 원소 N+M개 중 어느 하나는 반드시 제자리를 찾아가기 때문에 O(N+M)임을 알 수 있습니다.


https://github.com/encrypted-def/BOJ/blob/master/11728.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 11404번: 플로이드  (0) 2018.01.05
[BOJ] 1717번: 집합의 표현  (0) 2018.01.05
[BOJ] 2042번: 구간 합 구하기  (0) 2018.01.03
[BOJ] 1931번: 회의실배정  (3) 2018.01.03
[BOJ] 1937번: 욕심쟁이 판다  (0) 2018.01.03
[BOJ] 2512번: 예산  (0) 2018.01.03
  Comments