글 읽기 - 시간초과의 이유?

dmswl022329 1년 전 0

머지소트는 잘 구현한거 같은데

K번째 더해지는 숫자를 구하는데 오래걸리네요

방법이 있을까요?

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

int N, K, cnt = 0;
vector<int> A(500005);

void merge(vector<int> &a, int p, int q, int r){
    int i = p, j = q + 1, t = 0;
    vector<int> temp(500005);
    while(i <= q && j <= r){
        if(a[i] <= a[j]){
            temp[t++] = a[i++];
        }else{
            temp[t++] = a[j++];
        }
    }
    while(i <= q){
        temp[t++] = a[i++];
    }
    while(j <= r){
        temp[t++] = a[j++];
    }
    i = p, t = 0;
    
    while(i <= r){
        a[i++] = temp[t++];
    }
    // 저장을 다 하면 r-p+1 번 저장을 한다
    cnt += (r-p+1);
    if(cnt > 0 && cnt >= K){
    	cout << temp[K - cnt + r - p];
    	cnt = -1234567890;
    }
    
}

void merge_sort(vector<int> &a, int p, int r){
    if(p < r){
        int q = (p+r)/2;
        merge_sort(a, p, q);
        merge_sort(a, q+1, r);
        merge(a, p, q, r);
    }
}

int main() {
    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> A[i];
    merge_sort(A, 0, N-1);
    if(cnt > 0 && cnt < K) cout << -1;
	return 0;
}

wnwoghd22 1년 전 1

merge 함수 안의 temp 벡터를 static으로 선언하거나 전역변수로 꺼내면 통과다 되네요.

왜인지는 모르겠지만 객체 생성이 오래 걸리나봐요...

dmswl022329 1년 전 0

아 그쪽에서 문제가 있던거군요...

하긴 함수 호출할때마다 새 객체를 생성하니 그러겠네요

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

문제

문제

출처

ICPC

시간초과의 이유?

dmswl022329 1년 전 0

wnwoghd22 1년 전 1

dmswl022329 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말