백준(BOJ) 11728 배열 합치기 C++ 풀이

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

11728번: 배열 합치기

문제 풀이에 이용된 알고리즘: 정렬, 투 포인터

 

두 배열을 합치고, 오름차순 정렬한 결과를 출력하는 문제이다.

 

가장 간단히 떠올릴 수 있는 방법으로는, 하나의 배열에 모든 원소를 입력 받고 sort 함수를 이용하는 것이다.

 

이 방법으로 문제를 풀었을 때 생각보다 수행 시간이 너무 길어서, 혹시 투 포인터를 이용하면 조금 다른 성능(느리거나, 빠르거나)이 나타날 수 있는 지 궁금하여 실험을 진행했다.

 

투 포인터 방식을 이용하려면 a배열(arr1)과 b배열(arr2)를 사전에 오름차순 정렬을 해두고, 두 배열의 앞부분부터 비교하며 더 작은 값을 arr라는 새로운 배열로 옮기도록 한다. 이 때, 두 배열 별로 각자의 포인터(인덱스)를 두도록 한다.

 

실제 수행 결과, 해당 문제에서는 투 포인터가 20% 이상 빠른 모습을 보여주긴 했으나 여전히 긴 시간이 걸리는 것을 확인할 수 있었다.

 

/* BOJ 11728 배열 합치기 */
/* 투포인터 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
//int n, m, arr[2000002]; // sort를 이용한 풀이에 사용되는 변수
int n, m, arr1[1000001], arr2[1000001], arr[1000001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
 
    /* sort 함수를 이용한 정렬 풀이 */
    /*for (int i = 1; i <= n + m; i++)
        cin >> arr[i];
    
    sort(arr + 1, arr + 1 + n + m);
 
    for (int i = 1; i <= n + m; i++)
        cout << arr[i] << ' ';
 
    cout << endl;*/
 
    /* 투 포인터를 이용한 풀이 */
    for (int i = 1; i <= n; i++)
        cin >> arr1[i];
    for (int i = 1; i <= m; i++)
        cin >> arr2[i];
    
    // arr1과 arr2의 오름차순 사전 정렬
    sort(arr1 + 1, arr1 + 1 + n);
    sort(arr2 + 1, arr2 + 1 + m);
 
    int arr1_idx = 1, arr2_idx = 1;
    for (int i = 1; i <= n + m; i++)
    {
        if (arr1_idx > n) // 이미 arr1 배열의 모든 원소를 arr로 옮긴 상태면
            arr[i] = arr2[arr2_idx++]; // arr2의 원소를 arr에 옮김
        else if (arr2_idx > m) // 이미 arr2 배열의 모든 원소를 arr로 옮긴 상태면
            arr[i] = arr1[arr1_idx++]; // arr1의 원소를 arr로 옮김
        // arr1과 arr2 중 더 작은 값을 갖는 원소를 arr로 옮기고 포인터 증가
        else if (arr1[arr1_idx] < arr2[arr2_idx])
            arr[i] = arr1[arr1_idx++];
        else if (arr1[arr1_idx] >= arr2[arr2_idx])
            arr[i] = arr2[arr2_idx++];
    }
 
    for (int i = 1; i <= n + m; i++)
        cout << arr[i] << ' ';
 
    cout << endl;
 
    return 0;
}