백준 - 11004번 K번째 수

K번째 수

음 구현했는데 퀵소트로 틀렸다. 시간 초과임... 아마도 pivot을 맨 오른쪽으로 잡아서 그런거 같다.

 

그래서 가운데로 잡았는데 이번에는 틀렸다. 코드가 문제인걸까? ㅠ

 

사실 <algorithm>의 sort를 사용하니까 맞았다.ㅠ 내가 틀린거긴 한데 

 

일단 힙 소트를 구현해보자. 이건 최악의 시간 복잡도가 O(nlogn)이니까.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include<cstdio>
#include<iostream>

using namespace std;

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

int partition(int left, int right, int arr[]) {
	int pivot = arr[right];
	int i, j;
	i = left;
	j = left;

	if (left >= right)return left;

	while (j<right) {
		if (pivot > arr[j]) {

			swap(&arr[i], &arr[j]);
			i++;
		}
		j++;
	}
	swap(&arr[right], &arr[i]);

	return i;
}

void sort(int left, int right, int arr[]) {
	if (left < right) {
		int pivot = partition(left, right, arr);

		sort(left, pivot - 1, arr);
		sort(pivot + 1, right, arr);
	}
}


int N, K;
int arr[5000001];

int main() {
	//ios::sync_with_stdio(false);

	//freopen("input.txt", "r",stdin);

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int tmp;
		scanf("%d", &tmp);
		arr[i] = tmp;
	}
	sort(0, N - 1, arr);
	cout << arr[K - 1] << "\n";

	return 0;
}

시간 초과 코드. 위

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

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

int partition(int left, int right, int arr[]) {
	int piv_ind = (left + right) / 2;
	int pivot = arr[piv_ind];
	int i, j;
	i = left;
	j = left;

	while (j<piv_ind) {
		if (pivot > arr[j]) {

			swap(&arr[i], &arr[j]);
			i++;
		}
		j++;
	}
	swap(&arr[piv_ind], &arr[i]);

	return i;
}

void qsort(int left, int right, int arr[]) {
	if (left < right) {
		int pivot = partition(left, right, arr);

		qsort(left, pivot - 1, arr);
		qsort(pivot + 1, right, arr);
	}
}


int N, K;
int arr[5000001];

int main() {
	//ios::sync_with_stdio(false);

	//freopen("input.txt", "r",stdin);

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int tmp;
		scanf("%d", &tmp);
		arr[i] = tmp;
	}
	qsort(0, N - 1, arr);
	
	cout << arr[K - 1] << "\n";

	return 0;
}

틀린 코드 위.

 

 

음 근데 힙소트로 했는데 틀렸다.

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define MAXV 5000001

using namespace std;

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

int getSmall(int a, int b,int arr[]) {
	if (arr[a] < arr[b])return a;
	else return b;
}

class Heap {
private :
	int arr[2 * MAXV + 1];
	int Size = 0;
public: 
	void push(int x);
	int pop();
};

void Heap::push(int x) {
	Size++;
	arr[Size] = x;

	int child, parent;
	child = Size;
	parent = child / 2;

	while (parent > 0) {
		if (arr[child] < arr[parent]) {
			swap(&arr[child], &arr[parent]);
		}
		else { break; }
	}
}

int Heap :: pop() {
	int ret = arr[1];
	swap(&arr[1], &arr[Size]);
	Size--;
	int parent, left, right;
	int smaller;

	parent = 1;

	left = parent * 2;
	right = parent * 2 + 1;
	smaller = left;
	if(right <= Size)
		smaller = getSmall(left, right,arr);

	while (smaller <= Size) {

		if (arr[smaller] < arr[parent]) {
			swap(&arr[smaller], &arr[parent]);
		}
		else {
			break;
		}

		left = parent * 2;
		right = parent * 2 + 1;
		smaller = left;
		if(right <= Size)
			smaller = getSmall(left, right, arr);
	}

	return ret;
}



int N,K;
Heap heap;

int main() {
	//ios::sync_with_stdio(false);
	/*
	freopen("input.txt", "r",stdin);

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int tmp;
		scanf("%d", &tmp);
		heap.push(tmp);
	}

	for (int i = 0; i < K-1; i++) {
		heap.pop();
	}
	cout << heap.pop() << "\n";
	*/


	heap.push(4);
	heap.push(-1);
	heap.push(8);
	heap.push(2);

	cout << heap.pop()<<"\n";
	cout << heap.pop() << "\n";
	cout << heap.pop() << "\n";
	cout << heap.pop()<<"\n";


	return 0;
}

 

음 long long int로 해도 틀린다. 자료형 문제가 아니라면 힙소트가 틀린건가 ㅠㅠ?ㅠ?ㅠ?ㅠ?ㅠ?

 

 

롱롱으로 할 필요는 없다. 2*10^9 까지 int가 표현하니까

 

근데 퀵소트의 최악의 경우가 예시에 포함되어 있는거 같다.

 

median of three를 공부해서 하자./..... 그래서 일단 내가 구현한 힙도 틑린거 같아서 stl의 priority_queue를 써서 힙소트를 구현하니까 맞았다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> q;
int N, K;

int main() {
	//freopen("input.txt", "r",stdin);
	ios_base::sync_with_stdio(false);
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		q.push(-tmp);
	}
	for (int i = 0; i < K - 1; i++) {
		q.pop();
	}
	cout << -q.top();
	return 0;
}