글 읽기 - 11004번 - qosrt -> 시간초과... 헬프미

gfdhq 4년 전 0

sort 함수 이용했는데 시간초과 떠서

qsort 이용했는데 마찬가지로 시간초과가 뜨네요... ㅠㅠ 도와주십쇼 행님덜

#include<iostream>
#include<limits.h>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdio>

#define NODE_MAX 100001

using namespace std;

int comp(const void* a, const void *b){
	return *(int*)a - *(int*)b;
}

int main(void){
	int n, k;
	cin >> n >> k;
	vector<int> v;
	for (int i = 0; i < n; i++){
		int data;
		cin >> data;
		v.push_back(data);
	}
	qsort(v.data(), v.size(), sizeof(int), comp);

	cout << v[k-1] << endl;
	return 0;
}

kyo20111 4년 전 0

cin cout이 너무 느려서 그렇습니다.

ios_base::sync_with_stdio(false); cin.tie(NULL);을 추가하면 sort를 사용한 코드가 맞습니다.

lim551 4년 전 0

FastIO 쓰십셔

그리고 퀵소트로 되는지는 모르겠는데 퀵 셀렉션으로 O(N)으로 푸는게 더 빠를겁니다

kyo20111 4년 전 0

https://www.acmicpc.net/problem/15552

lim551 4년 전 0

퀵 셀렉션은 아마 c++ stl의 nth_element로 구현되어 있을겁니더.

gfdhq 4년 전 0

행님덜 답변 고맙습니다. 그런데 제가 너무 한심해서 말을 못알아먹겠습니다.ㅜㅜ

djm03178 4년 전 4

입출력만 빠르게 하면 단순 sort로도 통과될 수 있고, 그를 위한 방법이 https://www.acmicpc.net/proble... 에 설명되어 있습니다.
원래 이 문제는 정렬을 하는 게 목적인 문제가 아닙니다. quickselect라는 알고리즘을 요구하는 문제이고, 이를 구현한 라이브러리 함수가 C++에 nth_element 라는 함수입니다.

gfdhq 4년 전 0

와 정말로 깔끔한 문제에 대한 정리 감사합니다. 도움을 많이 받고 잇네요... 고맙습니다.

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

문제

문제

출처

ICPC

11004번 - qosrt -> 시간초과... 헬프미

gfdhq 4년 전 0

kyo20111 4년 전 0

lim551 4년 전 0

kyo20111 4년 전 0

lim551 4년 전 0

gfdhq 4년 전 0

djm03178 4년 전 4

gfdhq 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말