글 읽기 - 어느 부분이 틀렸을까요?

hippohmh 6년 전 0

우선 제가 알고리즘이나 자료구조 지식이 부족하여 quick selection으로 짰음을 알려드립니다.

VC2015에서 돌릴 때는 잘 돌아가는 것 같은데 제출하면 틀렸다고 뜨네요.

어느 부분이 틀렸나요?

quick selectin으로 짜면 무조건 시간초과가 나오나요?

#include <stdio.h>
#include <malloc.h>

int partition(int* arr, int left, int right) {
	int index = left, i, temp;

	for (i = left; i<right; i++) {
		if (arr[i] <= arr[right]) {
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
			index++;
		}
	}

	temp = arr[index];
	arr[index] = arr[right];
	arr[right] = temp;

	return index;
}

int quickselection(int* arr, int left, int right, int k) {
	int pivot = partition(arr, left, right);
	int res;

	if (pivot == k)
		res = arr[pivot];
	else if (pivot < k)
		res = quickselection(arr, pivot + 1, right, k);
	else
		res = quickselection(arr, left, pivot - 1, k);

	return res;
}

int main() {
	int N, K, i;
	long long result = 0;
	int* arr;
	int* sub;

	scanf("%d %d", &N, &K);

	arr = (int*)malloc(sizeof(int)*N + 1);

	for (i = 1; i <= N; i++)
		scanf("%d", &arr[i]);

	for (i = 1; i <= N - K + 1; i++) {
		result += quickselection(arr, i, K + i - 1, (i + K + i - 1) / 2);
	}

	printf("%lld \n", result);

	return 0;
}

djm03178 6년 전 0

quick selection이 기존의 배열 자체를 변경하기 때문에 이 방법으로는 원소들의 순서가 망가져서 잘 안 될 것 같습니다. 굳이 한다면 매번 범위만큼 다른 배열에 복사해두고 찾을 수는 있겠지만, 제가 988ms에 통과시켰던 조금 무식한(?) 방법보다 느릴 것 같아서, 아마도 어렵지 않나 생각합니다.

djm03178 6년 전 0

마침 아이디어가 하나 떠올라서 다시 풀어서 56ms에 통과했네요. C나 C++로 O(nk)시간에 최대한 최적화해서 가까스로 AC를 띄우는 것도 가능은 하지만, 잘 만들면 O(n lg k) 시간에 해결하는 게 가능하네요. 그쪽을 잘 생각해보시면 좋을 듯합니다.

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

문제

문제

출처

ICPC

어느 부분이 틀렸을까요?

hippohmh 6년 전 0

djm03178 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말