글 읽기 - 시간초과와 런타임에러가 자꾸 나요

parkkpu 7년 전 0

두가지 방법으로 해봤는데 문제가 무엇인지 모르겠습니다.

하나는 런타임에러 하나는 시간초과라고 뜨네요.

문제가 무엇인지 모르겠습니다.

도와주세요ㅜㅜ

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int arr[100002];

int main(){
    
    int n;
    int k;
    
    scanf("%d",&n);
    scanf("%d",&k);
    
    for(int i=0; i<n; i++){
        scanf("%d",&arr[i]);
    }
    
    sort(arr,arr+n);
    
    printf("%d",arr[k-1]);
    
    return 0;
}



//위의 코드로 실행하면 런타임 에러가 나고



#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    
    int n;
    int k;
            
    scanf("%d",&n);
    scanf("%d",&k);
    
    int arr[n];
    
    for(int i=0; i<n; i++){
        scanf("%d",&arr[i]);
    }
    
    sort(arr,arr+n);
    
    printf("%d",arr[k-1]);
    
    return 0;
}

//이 코드를 실행하면 시간 초가가 나네요

highalps 7년 전 1

N이 상당히 크기 때문에, 일반적인 sort 함수로는 답을 구해내기 힘듭니다.

제가 알기론, C++에서의 sort 함수는 대략적으로 퀵소트로 돌아가는 것으로 알고 있는데, 퀵소트는 worst case인 경우 시간 복잡도가 O(n^2) 입니다.

따라서 무조건 O(nlogn)의 시간 복잡도를 가지는 merge sort를 직접 구현 해보시거나 (이것도 맞을지는 확실히 모르겠습니다)
아니면 Quick selection 에 대해서 찾아보시는 게 좋을 것 같습니다.

혹은 nth_element 라는 k번째 위치한 element를 찾는 함수가 있는데, 역시 Quick selection에 대해서 선행하시고 난 뒤 사용하는 것을 추천합니다

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

문제

문제

출처

ICPC

시간초과와 런타임에러가 자꾸 나요

parkkpu 7년 전 0

highalps 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말