728x90
시간 제한 : 1.5초
메모리 제한 : 256MB
입력
첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)
둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절대값이 109보다 작거나 같은 정수이다.
출력
첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.
소스코드
#include <iostream> #include <vector> using namespace std; int main(void) { ios_base::sync_with_stdio(false); int m, n, idx1, idx2; cin >> n >> m; vector<int> arr1(n), arr2(m), ans(n+m); for (int i = 0; i < n; i++) cin >> arr1[i]; for (int i = 0; i < m; i++) cin >> arr2[i]; idx1 = idx2 = 0; for (int i = 0; i < n + m; i++) { if (idx1 >= n) ans[i] = arr2[idx2++]; else if (idx2 >= m) ans[i] = arr1[idx1++]; else { if (arr1[idx1] < arr2[idx2]) ans[i] = arr1[idx1++]; else ans[i] = arr2[idx2++]; } } for (int i = 0; i < n + m; i++) cout << ans[i] << ' '; }
Tip
Merge Sort(합병 정렬)을 응용하는 문제로 두 배열의 요소끼리 비교하면서 하나의 배열을 완성하는 간단한 문제다.
728x90
'Computer Science > Algorithm Problem' 카테고리의 다른 글
백준] 14720 - 우유 축제(충남대학교 생각하는 프로그래밍 대회) (0) | 2018.08.08 |
---|---|
백준] 5566 - 주사위 게임(JOI 2010 예선) (0) | 2018.08.05 |
백준] 2858 - 기숙사 바닥(COCI 2010/2011) (0) | 2018.08.03 |
백준] 2003 - 수들의 합2 (0) | 2018.08.01 |
백준] 14697 - 방 배정하기(KOI 2017 전국 - 초등부, 중등부) (0) | 2018.07.29 |