글 읽기 - 질문좀 드리겠습니다!

jh0956 4년 전 0

quick selection 을 찾아보고 어떤 방식인지 공부하였으며

기존에 알고있던 quick sort 구현법을 이용해서 문제를 풀어보았는데

수없는 시간초과끝에 질문을 드리게 되었습니다.

아무리봐도 quick 부분에 문제는 없어보이는데

partition 알고리즘이 이 문제를 풀기에 적합하지 않은 정렬코드인걸까요?

#include <cstdio>
#pragma warning(disable:4996)
int arr[5000001];
int N, K;
bool check = false;

int partition(int s, int e) {
	int pivot = arr[s];
	int k = s, temp;
	for (int i = s + 1; i <= e; i++) {
		if (pivot > arr[i]) {
			k++;
			temp = arr[k];
			arr[k] = arr[i];
			arr[i] = temp;
		}
	}
	arr[s] = arr[k];
	arr[k] = pivot;
	pivot = k;

	return pivot;
}

void quick(int s, int e) {
	if (check) return;
	int pivot;
	if (s < e) {
		int pivot = partition(s, e);
		if (pivot == K - 1) {
			check = true;
			return;
		}
		if(K-1 < pivot)quick(s, pivot - 1);
		if (check) return;
		if(pivot < K-1)quick(pivot + 1, e);
	}
}

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

djm03178 4년 전 1

https://www.acmicpc.net/board/...

jh0956 4년 전 0

공지 읽고 질문드렸었던건데 제대로 안읽었나봅니다

quickselection 이 quicksort에 조건만 주면 되는 것인줄 알았는데 다른 알고리즘이였네요!

새로운 stl 함수도 알아가게 되어서 큰 도움되었습니다.

quick selection 공부해서 문제 풀어볼려구요! 감사합니다 djm03178님

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

문제

문제

출처

ICPC

질문좀 드리겠습니다!

jh0956 4년 전 0

djm03178 4년 전 1

jh0956 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말