[분할정복]11728 배열합치기(C++)

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

 

에

뭐지

 

그냥 두개 다 입력받아서 SORT해볼가...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;

    int n_arr[n + m];

    for (int i = 0; i < n + m; i++)
    {
        cin >> n_arr[i];
    }
    sort(n_arr, n_arr + n + m);

    for (int i = 0; i < n + m; i++)
    {
        cout << n_arr[i] << " ";
    }
}

응..?

ㅋㅋㅋㅋㅋㅋㅋ

뭐지

..?

왜 된거지

 

분명 이렇게 풀라고 한 문제는 아닐테기까

sort 쓰지말고 내가 직접 풀어보자

 

여기서 중요한건

이미 "정렬된 배열 두개"

라는 것이고

 

정말 간단하게

입력받은 배열의 맨 앞 인덱스부터 

비교하면서 차례대로 넣어주면 끝...

#include <iostream>

#include <vector>

using namespace std;

int main()

{

    int n, m;

    cin >> n >> m;

    int n_arr[n], m_arr[m];

    for (int i = 0; i < n; i++)

    {

        cin >> n_arr[i];

    }

    for (int i = 0; i < m; i++)

    {

        cin >> m_arr[i];

    }

    int n_index = 0, m_index = 0, index = 0;

    int result[n + m];

    while (n_index < n && m_index < m)

    {

        if (n_arr[n_index] < m_arr[m_index])

        {

            result[index++] = n_arr[n_index++];

        }

        else

        {

            result[index++] = m_arr[m_index++];

        }

    }

    while (n_index < n)

        result[index++] = n_arr[n_index++];

    while (m_index < m)

        result[index++] = m_arr[m_index++];

    for (int i = 0; i < n + m; i++)

    {

        cout << result[i] << " ";

    }

}

근데 놀랍게도 sort쓴것보다 시간도, 메모리 차지도 많이나옴

 

메모리차지는 뭐 당연히 result라는 함수까지 추가했으니 당연하고

 

흠. 정답률 높은이유가있었구만