글 읽기 - 9426 quick selection 문제...

dgmsky 6년 전 0

현재 quick selection으로 짜고 있으나, 틀렸습니다가 나오는 상황입니다.

quick selection이 quick sort 변형인 것으로 알고 있어서, partition2 함수처럼 짰다가, 메모리 초과가 나오길래 partition 함수형태로 짰는데도 틀렸다고 나오네요;;

어느 부분에 수정이 들어가야 하는지 감을 못잡겠습니다...

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

#include <iostream>

using namespace std;

void swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int* arr, int left, int right){
    int pivot = (left + right) / 2;

    swap(&arr[right], &arr[pivot]);

    for (int i = left; i < right; i++) {
        if (arr[i] < arr[right]) {
            swap(&arr[i], &arr[left]);
            left++;
        }
    }

    swap(&arr[left], &arr[pivot]);

    return left;
}

int partition2(int* arr, int left, int right){
    int first = left;
    int pivot = arr[first];
    left ++;
    while(left <= right){
        while(left < right && arr[left] <= pivot)
            left ++;
        while(left <= right && arr[right] > pivot)
            right --;

        if(left < right)
            swap(&arr[left], &arr[right]);
        else
            break;
    }

    swap(&arr[right], &arr[first]);
    return right;
}

int searchKth(int* arr, int left, int right, int target){
    if(left <= right){
        int index = partition(arr, left, right);
        int result;
        if(index == target){
            result = arr[index];
        }
        else if(index < target){
            result = searchKth(arr, index + 1, right, target);
        }
        else{
            result = searchKth(arr, left, index - 1, target);
        }
        return result;
    }
    return 0;
}

int main(){
    int N, K, minIndex;
    long long sum = 0;

    cin >> N >> K;
    minIndex = ((K+1)/2) - 1; // K 번째로 작은 index이므로 1을 빼준다

    int* arr = new int[N];

    for(int i = 0; i < N; i++)
        cin >> arr[i];

    for(int i = 0; i < N-K+1; i++){
        int* newArr = new int[K];
        for(int j = 0; j < K; j++)
            newArr[j] = arr[i+j];
        sum += searchKth(newArr,0,K-1,minIndex);
    }

    cout << sum;
    return 0;
}

daniel00 6년 전 1

이 문제는 아래 문제와 완전히 동일한 문제입니다.

https://www.acmicpc.net/proble...

최초 배열에서 맨앞데이터가 삭제되고 맨끝에 새로운 데이터가 삽입되므로

(1)펜윅트리를 구현해서 부분배열이 변경될때 마다 매번 위의 2포인트씩만 update()해주고 , (O(logN))

바이너리서치로(O(logN)) 중앙값을 찾아내는 방법으로 풀어보시면 될 겁니다.

펜윅트리에는 배열의 값이 출현하는 빈도수를 저장한다는점에 유의하세요.

고민하고계신 퀵셀렉트로 풀면 타임아웃에 걸릴듯합니다.

풀이에 성공하시길 바라겠습니다.

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

문제

문제

출처

ICPC

9426 quick selection 문제...

dgmsky 6년 전 0

daniel00 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말