글 읽기 - Merge sort로 풀어봤는데 시간초과

hsh21097305 1년 전 0

그냥 STL의 sort함수 쓰면 되는건 알고있지만 직접해보고싶어서 구글링해서 공부했던 merge sort로 풀어봤더니 시간초과가 나옵니다. merge sort는 O(nlogn)이라 괜찮을줄알았는데 제가 구현을 잘못한것같네요. 틀린 부분이나 안되는 이유 알려주세요.

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

using namespace std;

int n;
vector<vector<int>> v;

void merge(int left, int right)
{
    int mid = (left+right)/2;
    int i = left;
    int j = mid+1;
    int c = left;
    int temp[n][2] = {0};
    while (i<=mid && j<=right)
    {
        if (v[i][0] < v[j][0])
        {
            temp[c][0] = v[i][0];
            temp[c++][1] = v[i++][1];
        }
        else if (v[i][0] > v[j][0])
        {
            temp[c][0] = v[j][0];
            temp[c++][1] = v[j++][1];
        }
        else if (v[i][0] == v[j][0])
        {
            if (v[i][1] < v[j][1])
            {
                temp[c][0] = v[i][0];
                temp[c++][1] = v[i++][1];
            }
            else if (v[i][1] > v[j][1])
            {
                temp[c][0] = v[j][0];
                temp[c++][1] = v[j++][1];
            }
        }
    }
    while (i <= mid)
    {
        temp[c][0] = v[i][0];
        temp[c++][1] = v[i++][1];
    }
    while (j <= right)
    {
        temp[c][0] = v[j][0];
        temp[c++][1] = v[j++][1];
    }
    for (int k = left; k <= right; k++)
    {
        v[k][0] = temp[k][0];
        v[k][1] = temp[k][1];
    }
}

void divide(int left, int right)
{
    if (left != right)
    {
        int mid = (left+right)/2;
        divide(left,mid);
        divide(mid+1,right);
        merge(left,right);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    vector<int> tempV;
    int temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        tempV.push_back(temp);
        cin >> temp;
        tempV.push_back(temp);
        v.push_back(tempV);
        tempV.clear();
    }
    divide(0,n-1);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            cout << v[i][j] << " ";
        }
        cout << "\n";
    }
}

djm03178 1년 전 0

16번쨰 줄이 매우 비효율적입니다. 크기가 n인 배열을 만드는 데에는 O(n)의 시간이 걸리고, merge 함수가 총 O(n)번 호출되니 총 O(n^2)의 시간이 걸리게 됩니다.

실제로 merge가 사용할 인덱스는 left부터 right까지뿐이기 때문에, 이 이외의 공간을 추가로 만들었다가 삭제하는 것이 비효율적입니다. 미리 하나만 크게 할당해두고 재사용하는 것이 낫습니다.

hsh21097305 1년 전 0

알겠습니다 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Merge sort로 풀어봤는데 시간초과

hsh21097305 1년 전 0

djm03178 1년 전 0

hsh21097305 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말