[BOJ / C++] 배열 합치기 (정렬)

문제링크: https://www.acmicpc.net/problem/11728

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    vector<int> b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    vector<int> mergeList(n+m);
    
    int aidx = 0, bidx = 0;
    for (int i = 0; i < n+m; i++) {
        if (aidx == n) mergeList[i] = b[bidx++];
        else if (bidx == m) mergeList[i] = a[aidx++];
        else if (a[aidx] <= b[bidx]) mergeList[i] = a[aidx++];
        else mergeList[i] = b[bidx++];
    }

    for (int i: mergeList) {
        cout << i << ' ';
    }
}

 

 

2. 분석

aidx == n, bidx == m에 대한 처리가 중요하다. 3번째, 4번째 조건 처리만 있어도 되지 않나 생각할 수 있지만, aidx, bidx 인덱스를 증가시켜놓기 때문에 a[aidx], b[bidx]를 참조하는 순간 OOB 에러가 발생할 수 있다.

 

3. 시간복잡도

n+m번의 비교가 일어나므로 O(n+m)에 동작한다. 시간제한이 1초이고 n, m < 1,000,000이므로 2 * 10^6 < 10^8 이므로 시간내 통과가 가능하다.