글 읽기 - [C++] 중앙값 구하기: 시간초과 (질문 게시판 정주행 했습니다ㅠㅠㅠ)

jaywonchung 7년 전 0

처음엔 deterministic selection을 구현해서 풀다가 도저히 시간초과를 피할 수가 없어 다른 방법을 생각해보게 되었습니다.

input은 0~65535 사이에서 들어오므로, unsigned short count[65536];으로 선언한 array에 들어온 숫자의 개수를 기록합니다. 즉, n이 들어오면 count[n]++;를 해줍니다.

count를 보고 count[i]를 쭉 더하다가 더한 값이 (k+1)/2 이상이 되면 i-1이 중앙값이 되게 됩니다.

그리고 2%에서 시간초과가 뜹니다.....

count array를 쭉 진행하면서 값을 더하는 과정이 너무 오래 걸리는걸까요? 아니면 혹시 count에서 index를 찾아가는 게 오래 걸리나요?

고수님들의 조언을 구합니다ㅠㅠ

#include <iostream>
using namespace std;

int get_mid(unsigned short* count, int k){    //k개 수열의 중앙값을 구합니다.
    unsigned short index_sum = 0;
    int i = 0;
    
    while(index_sum < (k+1)/2){
        if(count[i]==0) continue;
        index_sum+=count[i++];
    }
    
    return i-1;
}

int main(int argc, const char* argv[]){
    
    int n,k;
    cin>>n>>k;
    long long sum = 0;
    unsigned short tmp;
    
    if(k==1){        //k가 1일 땐 input을 전부 더하는 것과 다음 없으므로 따로 했습니다. 
        for(int i = 0; i < n; i++){
            scanf("%hd", &tmp);
            sum+=tmp;
        }
        cout<<sum<<'\n';
        return 0;
    }
    
    unsigned short count[65536] = {0};    //n이 입력되면 count[n]++;을 해서 저장합니다.
    unsigned short* history = new unsigned short[k];    //최근 k개의 숫자에만 관심이 있으므로 그걸 저장합니다. 
    
    for(int i = 0; i < k; i++){    //1번(index 0)부터 k-1번째(index k-2) 숫자는 그냥 저장만 합니다.
        scanf("%hd", &tmp);
        count[tmp]++;
        history[i] = tmp;
        if(i==k-1) sum = get_mid(count, k);    //k번째(index k-1)는 중앙값을 구해 sum에 더하기 시작합니다.
    }
    
    for(int i = k; i < n; i++){    //k+1(index k)번째부턴 k-1개 전에 나왔던 숫자를 count에서 지워줘야 합니다. 이때 history를 사용합니다.
        scanf("%hd", &tmp);
        count[history[i%k]]--;
        history[i%k] = tmp;
        count[tmp]++;
        
        sum+=get_mid(count, k);
    }
    
    cout<<sum<<'\n';
    
    return 0;
}

koosaga 7년 전 0

65536*N (getmid = 최악 65536번 정도 연산) 이니 시간초과는 당연히 나야하고요

count 배열은 N번만 건드리니 문제가 없습니다.

koosaga 7년 전 0

시간 복잡도 개념에 대해서 공부하시는 것을 추천드립니다.

chogahui05 7년 전 0

일단 규칙을 먼저 찾아보시고

그게 안되신다면 게시판 몇 번 더 정주행 해 봅시다.

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

문제

문제

출처

ICPC

[C++] 중앙값 구하기: 시간초과 (질문 게시판 정주행 했습니다ㅠㅠㅠ)

jaywonchung 7년 전 0

koosaga 7년 전 0

koosaga 7년 전 0

chogahui05 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말