[백준] 11728번 배열 합치기

문제

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

풀이과정

머지소트 과정 중 두 개의 정렬 된 배열을 합치는 과정을 구현하는 문제이다.

처음에는 벡터를 이용해 구현하려 했지만 시간초과가 났다.

그 후에 머지소트에서 merge 과정대로 구현을 했고 맞을 수 있었다.

문제를 풀이하면서 또 하나 배운 사실이 있다.

나는 cin, cout의 사용이 더 편리하다고 생각해서 cin, cout을 쓰는데 속도 때문에 ios::sync_with_stdio(false)를 항상 맨 위에 쓰고 시작하는데 속도를 위한거라면 이것말고도 cin.tie(0)을 해줘야 된다고 한다.

실제로 cin.tie(0) 만을 추가해봤는데 속도가 더 빨라졌다 앞으로는 두 개를 무조건 맨 위에 쓰고 시작해야겠다.

소스코드

#include <iostream>

#define MAX 1000001

using namespace std;

int A[MAX];
int B[MAX];
int ans[MAX];
int N, M;

void merge()
{
    int i = 0; int j = 0; int k = 0;

    while (i < N && j < M)
    {
        if (A[i] <= B[j]) ans[k++] = A[i++];
        else ans[k++] = B[j++];
    }

    // 남은 배열의 원소들을 모두 넣는 과정
    while (i < N) ans[k++] = A[i++];
    while (j < M) ans[k++] = B[j++];
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> N >> M;

    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];

    int length = N + M;

    merge();

    for (int i = 0; i < length; i++)
    {
        cout << ans[i]; if (i != length - 1) cout << " ";
    }

    cout << "\n";

    return 0;
}