글 읽기 - "틀렸습니다" 질문 드립니다.

joonamin44 3년 전 0

quick select에서 최악의 경우 O(N^2) 까지 나올 수 있다는 것은 알고있습니다.

시간초과를 예상하고 코드를 짰는데 대략 7% 정도에서 틀렸습니다가 나옵니다.

제가 생각한 방식은

1. 배열에서 첫번째 원소를 pivot으로 잡은 뒤 pivot 보다 작은 원소는 less , 큰 원소는 larger, 같은 원소는 equal

에 저장하였습니다.

2. pivot 보다 작은 배열의 크기보다 k가 작을 경우 less 집합에 찾고자 하는 원소가 존재하므로 범위를 좁혔습니다.

3. less 와 equal 의 크기의 합 보다 k가 클 경우 찾고자 하는 원소는 larger에 존재하므로 k- abs(less) - abs(equal)

만큼 뺀 번지만큼 범위를 줄였습니다.

저 혼자 반례를 찾고자 여러번 시도했지만 좀 처럼 감이 잡히질 않습니다 ㅠㅠ..

혹시 반례나 어느 로직이 잘못됐는지 알려주실 수 있으신가요 ?ㅠㅠ

#include <iostream>
#include <vector>
using namespace std;
int quick_select(const vector<int>& arr, int k){
    vector<int> less, larger, equal;
    int size = arr.size();
    int pivot = arr[0];
    for(int i=0; i<size; i++){
        if( arr[i] < pivot )
            less.push_back(arr[i]);
        else if( arr[i] > pivot )
            larger.push_back(arr[i]);
        else
            equal.push_back(arr[i]);
    }
    // 3 분할
    if( less.size() > k )
        return quick_select(less, k);
    else if( less.size() + equal.size() < k )
        return quick_select(larger, k - less.size() - equal.size() );
    else
        return pivot;

}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N,K;
    cin >> N >> K;

    vector<int> arr(N);

    for(int i=0; i<N; i++){
        cin >> arr[i];
    }
    // Best : O(N) , WORST : O(N^2)
    cout << quick_select(arr, K);

    return 0;
}

djs100201 3년 전 0

저도 퀵소트를 직접구현 해본적은 없어서 모르겠지만 배열자체를 parameter로 넘겨주게 되는 부분에서 시간초과가 나는것 같습니다.

추가로 c++은 알고리즘 헤더에 quick sort stl을 제공하니 참고하시기 바랍니다.

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

문제

문제

출처

ICPC

"틀렸습니다" 질문 드립니다.

joonamin44 3년 전 0

djs100201 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말