글 읽기 - quick selection을 사용하는 것 아닌가요??

haung921209 6년 전 0

시간 초과가 나오네요.......

quick selection 사용하는 것이 아닌가요 아님 제가 구현 방법을 바꿔야 할까요

#include <iostream>
#include <algorithm>
#define ull unsigned long long
using namespace std;
unsigned int quick_selection(int n, unsigned int *ArrList, int k);
int main(void) {
    int n,k;
    cin>>n>>k;
    unsigned int* container;
    container=new unsigned int [n+1];
    for(int i=0;i<n;i++)
        cin>>container[i];
    unsigned int resultvalue=quick_selection(n,container,k-1);
    cout<<resultvalue<<endl;
    
    
    
    
    return 0;
}


unsigned int quick_selection(int n, unsigned int *ArrList, int k)
{
    if (ArrList == NULL || n <= k)
        return -1;
    
    int start = 0;
    int end      = n - 1;
    
    while (start < end)
    {
        int i = start;
        int j = end;
        int mid = ArrList[(i + j)/2];
        
        while (i < j)
        {
            if(ArrList[i] >= mid)
            {
                int tmp = ArrList[j];
                ArrList[j] = ArrList[i];
                ArrList[i] = tmp;
                j--;
            } else {
                i++;
            }
        }
        
        if (ArrList[i] > mid)
            i--;
        
        if (k <= i)
            end = i;
        else
            start = i + 1;
    }
    
    return ArrList[k];
}

simm4256 6년 전 0

정렬하고 k번 인덱스 출력하면 되는거 아닌가요?

haung921209 6년 전 0

아뇨 500만개를 정렬하면 타임아웃이 나올거에요!

simm4256 6년 전 0

500만개를 정렬하는데 왜 타임아웃이 나오죠?

simm4256 6년 전 0

잘만 되는데요???

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

int main(){
    int n,k,a[5000001];
    cin >> n >> k;
    int i;
    for(i=0;i<n;scanf("%d",a+i++));
    sort(a,a+n);
    printf("%d",a[k-1]);
}

haung921209 6년 전 0

오.....

동적할당으로 저장 배열을 만들어주는 것 밖에 다른 것이 없는데

저는 시간 초과가 났었거든요........

accept되었네요 흠......

감사합니다 ㅎㅎ

haung921209 6년 전 0

제가 처음 사용했던 소스입니다.

여기서 동적할당 부분만 차이가 있네요

+)찾아보니 동적할당의 경우에는 다이나믹 바인딩이기 때문에 상대적으로 시간 낭비가 더 크고, 따라서 시간 초과의 경우가 더 많다고 생각해도 무방할 것 같습니다.

#include <iostream>
#include <algorithm>
#define ull unsigned long long
using namespace std;

int main(void) {
    // insert code here...
    int n,k;
    cin>>n>>k;
    ull* container;
    container=new ull [n+1];
    for(int i=0;i<n;i++)
        cin>>container[i];
    sort(container,container+n);
    cout<<container[k-1]<<endl;
    
    
    return 0;
}

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

문제

문제

출처

ICPC

quick selection을 사용하는 것 아닌가요??

haung921209 6년 전 0

simm4256 6년 전 0

haung921209 6년 전 0

simm4256 6년 전 0

simm4256 6년 전 0

haung921209 6년 전 0

haung921209 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말