프로그래머스 - 정렬 : K번째 수, 가장 큰 수, H index

https://hongku.tistory.com/149

자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

정렬 코드 수정할때 참고 했다.

 

K번째 수

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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



void sort(int st, int dt, int*arr) {
	if (st >= dt) {
		return;
	}
	int end = dt;
	int pivot = st++;

	while (1) {
		while (st <= end && arr[st] < arr[pivot]) {
			st++;
		}
		while (dt >= pivot && arr[dt] > arr[pivot]) {
			dt--;
		}

		if (st < dt) {
			swap(&arr[st], &arr[dt]);
		}
		else {
			swap(&arr[dt], &arr[pivot]);
			break;
		}
	}

	sort(pivot, dt-1, arr);
	sort(dt+1, end, arr);

}


vector<int> solution(vector<int> array, vector<vector<int>> commands) {
	vector<int> answer;
	int arr[105];

	for (int i = 0; i < commands.size(); i++) {
		for (int j = 0; j < array.size(); j++)
		{
			arr[j] = array[j];
		}
		sort(commands[i][0] - 1, commands[i][1] - 1, arr);
		answer.push_back(arr[commands[i][2] + commands[i][0] - 2]);
	}
	return answer;
}

처음에 세그 떴었는데 sort(pivot, dt-1,arr); sort(dt+1,end,arr); 둘로 안하고 sort(pivot, dt,arr); sort(st,end,arr); 로 해서 틀렸었다. 나는 dt, st이렇게 한개 차이일 줄 알았는데 그게 아니라 dt , dt+1 ,st일 수도 있을듯?

 

그럼 이제 시간 초과 나는 부분을 해결해야 한다........

 

뭔가 command 처리할때 매번 저렇게 넣고 정렬 안해도 될거 같은데 잘 모르겠다.

아 삼성 숫자 야구 게임도 다시 풀어야 되는데. 다른 b형 문제들도. 갈길이 멀다...아아

 

 

아 생각해봤는데 그냥 내가 구현한 퀵소트가 문제인거 같아서 유트브를 보고 다시 했다.

유트브는 이걸 보았따. https://www.youtube.com/watch?v=cWH49IKDIiI

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

int partition(int *arr, int l, int r) {
	int pivot = arr[r];
	int i = l - 1;

	for (int j = l; j <= r - 1; j++) {
		if (arr[j] <= pivot) {
			i++;
			swap(&arr[i], &arr[j]);
		}
	}
	swap(&arr[i + 1], &arr[r]);
	return (i + 1);
}



void sort(int st, int dt, int*arr) {
	if (st < dt) {
		int p = partition(arr,st, dt);
		sort(st, p - 1, arr);
		sort(p + 1, dt, arr);
	}
}


vector<int> solution(vector<int> array, vector<vector<int>> commands) {
	vector<int> answer;
	int arr[105];

	for (int i = 0; i < commands.size(); i++) {
		for (int j = 0; j < array.size(); j++)
		{
			arr[j] = array[j];
		}
		sort(commands[i][0] - 1, commands[i][1] - 1, arr);
		answer.push_back(arr[commands[i][2] + commands[i][0] - 2]);
	}
	return answer;
}

난 맨 왼쪽을 피벗으로 잡았는데, 유트브는 맨 오른쪽을 피벗으로 잡았다. ㅠ

다시 해보장

 

가장 큰 수

음

[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

이게 정렬하면 될거 같은데 그냥 앞에서 부터 숫자가 큰게 먼저 오면 될거 같은데

 

3, 30, 34 같은건 어떻게 하지 

 

음 내생각에는 짧은게 먼저가 아니네

 

3,30,32,5,9 였으면 9533230 인데 , 길다고 먼저 오는건 아니란 소리.....

 

예시가 

3,32,34,30

음 길이가 같은건 그냥 뒤에 자리도 큰게 먼저 오면 된다 근데

3,34,312 같이 길이가 다른건 어떡하지?

34 3 312

 

5,52,581,5391  답은 58155391552

 

5 < 52 이면 5는 55라고 취급하고 비교하면 될듯?!! 자리가 짧으면 그냥 

 

511 53 비교하면 514  515

514 51

51 514

 

41 > 32 

 

414 <-  412

 

41412

 

음 연산자 오버로딩으로 구현해 볼랬는데 왜 안되는지 모르겠다. < 적용이 안된다.

 

음 일단 보류...

 

다시 도전한다.

 

다시 보니까 음 그냥 순열 문제인거 같다. 음 근데 다 돌리자니 10만개라서 10만! 로 말이 안된다. ㅋㅋ

그래서 정렬같은데 자릿수가 다르면 짧은 놈은 같은 곳까지만 인덱스를 변화시켜서 비교했다.

근데 36.4점으로 틀렸다. 음 정렬이 문제일 수 도 있다 ㅋㅋ

 

#include <string>
#include <vector>

using namespace std;
int arr[100001];
long long int maxv;
string ans = "";

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

bool compareAisBigger(int a, int b) {
	string A, B;
	A = to_string(a);
	B = to_string(b);

	//big one.
	int Size = A.size() > B.size() ? A.size() : B.size();
	
	int m=0,n=0;
	for (int i = 0; i < Size; i++) {
		if (A[m] > B[n] ) {
			return true;
		}
		else if (A[m] < B[n]) {
			return false;
		}

		if (m < A.size()-1) {
			m++;
		}
		if (n< B.size()-1) {
			n++;
		}
	}
}

int partition(int left, int right, vector<int>& numbers) {
	int pivot = right;
	int i, j;
	i = left;
	j = left;

	while (j < right) {
		if (compareAisBigger(numbers[j],numbers[pivot])) {
			swap(&numbers[i], &numbers[j]);
			i++;
		}
		j++;
	}
	swap(&numbers[pivot], &numbers[i]);

	return i;
}

void qsort(int left, int right, vector<int>& numbers) {

	if (left < right) {
		int pivot = partition(left, right, numbers);
		qsort(left, pivot - 1, numbers);
		qsort(pivot + 1, right, numbers);
	}
}


string solution(vector<int> numbers) {
	string answer = "";

	qsort(0, numbers.size() - 1, numbers);


	for (int i = 0; i < numbers.size(); i++) {
		answer += to_string(numbers[i]);
	}

	return answer;

}


int main() {

	vector<int> tmp;
	tmp.push_back(3);
	tmp.push_back(30);
	tmp.push_back(34);
	tmp.push_back(5);
	tmp.push_back(9);


	solution(tmp);

}

 

 

 

H index

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

[3, 0, 6, 1, 5]

3

여기서 hindex는 0~6사이 값일텐데

0일때는 0이상인게 몇개인지. 이하인게 몇개인지.

1일때는 1이상인게 몇개인지, 이하인게 몇개인지.

2

....

이러면 인용횟수가 10^4 이고 10^3만큼 길이니까 10^7번 음 할만한듯?

 

인용 횟수를 정할때 10^4 번하면 너무 많으니까 이분탐색으로 조정하면 좋을듯?

 

다시 생각해보았다.

음 정렬해보면

배열값 0 1 3 5 6

인덱스 0 1 2 3 4

 

2, 5-2

3개,3개

인덱스만 알아도 그 앞뒤로 갯수를 알 수 있다.

 

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다.

 

정렬 했을때 가운데에 위치하는 인용횟수가 h이다.

 

근데 중복된게 있으면?

0 1 3 3 5 6

0 1 2 3 4 5

 

3이상이 4개

나머지 논문중 3이하가 2개다.

 

음 근데 가운데 위치한 인용횟수는 중복되어도 괜찬다. 어차피 증가해도 h편 이상이라는거니까.

 

 

 

음 근데 틀렸따. ㅋㅋ

 

일단 vector는 call by value이다.!!! 이건 햇갈렸는데 명확히 하자.

 

근데 왜틀렸지...

 

#include <string>
#include <vector>
#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[]) {

	int pivot = partition(left,right,arr);
	if(left < pivot-1)
		sort(left, pivot-1, arr);
	if(pivot+1 < right)
		sort(pivot + 1, right, arr);
	
}


int solution(vector<int> citations) {
	int answer = 0;

	int arr[1001];

	for (int i = 0; i < citations.size(); i++) {
		arr[i] = citations[i];
	}

	sort(0, citations.size() - 1, arr);

	answer = arr[citations.size() / 2];
	for (int i = 0; i < citations.size(); i++) {
		cout << arr[i]<<"\n";
	}

	return answer;
}


void main() {
	vector<int> arr;
	arr.push_back(3);
	arr.push_back(0);
	arr.push_back(6);
	arr.push_back(1);
	arr.push_back(5);

	solution(arr);
}

 

 

H-index 다시 푸는데, 질문하기 좀 보니까 문제에 빠진 조건이라는게 가장 큰 값을 고르는거 같음 주어진 인용 회수 중에 그렇게 구현했는데

#include <string>
#include <vector>
#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 pivot = arr[right];
	int i, j;
	i = left;
	j = left;

	while (j<right) {
		if (pivot > arr[j]) {
			swap(&arr[i], &arr[j]);
			i++;
		}
		j++;
	}
	swap(&arr[right], &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);
	}
}

/*
1 3 3 8 8 8 8
0 1 2 3 4 5 6
3번 이상 인용이 6번
3번 이하 인용이 1번
*/

int solution(vector<int> citations) {
	int answer = 0;

	int arr[1001];

	for (int i = 0; i < citations.size(); i++) {
		arr[i] = citations[i];
	}
	//qsort(0, citations.size() - 1, arr);
	sort(citations.begin(), citations.end());
	int Size = citations.size();
	for (int i = 0; i < Size; i++) {
		if ((arr[i] > i || i==0) && Size - i >= arr[i]) {
			//	cout << i << "\n";
			answer = arr[i];
		}
	}

	cout << answer<<"\n";

	return answer;
}

int main() {
	vector<int> tmp;
	tmp.push_back(2);
	tmp.push_back(7);
	tmp.push_back(5);
	solution(tmp);
}

틀림 근데 6.7점으로 한개 맞음;