프로그래머스 - 이분 탐색 : 예산, 입국 심사,

음 비형 대비 내가 일단 다 구현해 보는데 벡터 값은 정렬을 어떻게 하지? 콜 바이 레퍼런스로 넘기면 될듯??

 

일단 정렬 코드를 작성했다. 파티션 부분에서 while문 종료되고 마지막에 피벗이랑 i 위치랑 스왑하는걸 빼먹어서 안됬었다. left<right 조건도 빼먹었었고.

 

#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 left, int right,vector<int>&budgets) {
	int pivot = (left + right) / 2;
	int i, j;


	i = left;
	j = left;

	while (j < right) {
		if (budgets[pivot] > budgets[j]) {
			swap(&budgets[i], &budgets[j]);
			i++;
		}
		j++;
	}
	swap(&budgets[pivot], &budgets[i]);
	return i;
}

void qsort(int left,int right,vector<int>&budgets) {
	if (left < right) {
		int pivot = partition(left, right, budgets);
		qsort(left, pivot - 1, budgets);
		qsort(pivot + 1, right, budgets);
	}

}

int solution(vector<int> budgets, int M) {
	int answer = 0;

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

	/*
	for (int i = 0; i < budgets.size(); i++) {
		cout << budgets[i] << " ";
	}
	cout << "\n";
	*/


	return answer;
}

void main() {
	vector<int> budgets;
	budgets.push_back(120);
	budgets.push_back(110);
	budgets.push_back(140);
	budgets.push_back(150);

	solution(budgets, 485);
}

 

아 근데 이분탐색하려고 보니까 이 문제는 굳이 정렬할 필요가 없는 문제다...... 중간 값을 찾으려는게 아니라 예산액을 정하는거라서?

 

이분탐색 하려면 시작값, 끝값이 있어야 되는데 내가 보기엔 배열의 최솟값과 최댓값으로 하면 될거같다.

 

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

using namespace std;

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

int partition(int left, int right,vector<int>&budgets) {
	int pivot = (left + right) / 2;
	int i, j;


	i = left;
	j = left;

	while (j < right) {
		if (budgets[pivot] > budgets[j]) {
			swap(&budgets[i], &budgets[j]);
			i++;
		}
		j++;
	}
	swap(&budgets[pivot], &budgets[i]);
	return i;
}

void qsort(int left,int right,vector<int>&budgets) {
	if (left < right) {
		int pivot = partition(left, right, budgets);
		qsort(left, pivot - 1, budgets);
		qsort(pivot + 1, right, budgets);
	}

}

int checkAndReturnBudgets(vector<int>&budgets, int limit) {
	int ans = 0;

	for (int i = 0; i < budgets.size(); i++) {
		if (budgets[i] <= limit) {
			ans += budgets[i];
		}
		else {
			ans += limit;
		}
	}
	return ans;
}

int findLimit(vector<int>&budgets,int M) {
	int Left = budgets[0];
	int Right = budgets[budgets.size() - 1];
	int nbudget;
	int Mid;

	int ans=0;

	while (Left <= Right) {
		Mid = (Left + Right) / 2;

		nbudget = checkAndReturnBudgets(budgets, Mid);

		if (nbudget < M ) {
			Left = Mid + 1;
			if (ans < Mid) { ans = Mid; }
		}
		else if (nbudget > M) {
			Right = Mid - 1;
		}
	}

	return ans;
}


int solution(vector<int> budgets, int M) {
	int answer = 0;

	//qsort(0, budgets.size() - 1, budgets);
	sort(budgets.begin(), budgets.end());
	/*
	for (int i = 0; i < budgets.size(); i++) {
		cout << budgets[i] << " ";
	}
	cout << "\n";
	*/
	answer = findLimit(budgets,M);

	return answer;
}

void main() {
	vector<int> budgets;
	budgets.push_back(120);
	budgets.push_back(110);
	budgets.push_back(140);
	budgets.push_back(150);

	solution(budgets, 485);
}

 95점인데 두개를 고쳤다. 이분 탐색에서 Left < Right 에 등호를 추가하니까 95점 까지 올라가고 빼면 25점

그리고 내가 구현한 소트를 사용하면 더 떨어진다.... 소트 뭐가 틀린거고 5점은 왜 틀린거지?

 

아 질문하기 보고 알았다... 이분 탐색의 범위는 진짜 가능한 범위를 주는게 맞다..

 

https://programmers.co.kr/learn/questions/8315읽어보면 Left를 0부터 해야 9번이 맞는다.

 

음 그리고 내가 위에 구현한 퀵소트는 맨 오른쪽을 피벗으로 잡을때 기준인거 같다. 왜 저 코드에서 가운데를 잡으면 안되나 고민해봤는데, 가운데 피벗을 기준으로 우측이 정리가 안된다... 아니 근데 역시나 K번째 수는 시간초과가 뜬다.

 

그러한 코드는 http://forums.codeguru.com/showthread.php?465373-RESOLVED-Quicksort-using-median 이것이 맞는듯 양쪽다 스왑해주는 방식으로

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> budgets, int M) {
    int answer = 0;
    int numbers = budgets.size();

    sort(budgets.begin(),budgets.end());

    for(auto itr=budgets.begin(); itr!= budgets.end(); itr++){
        if(*itr > (M / numbers)) return M/numbers;
        else{
            M -= *itr;
            numbers--;
        }
    }

    return budgets.back();
}

이렇게 한 분도 있는데 이건 어떻게 한건지 잘 이해는 안된다. ㅋㅋ...ㄹ아아아

 

 

 

입국 심사

음 문제를 읽었는데 어떻게 푸는지 잘 모르겠다.

 

모든 사람이 입국 심사를 받는데 걸리는 시간이라.....

 

그 시간을 이분 탐색으로 가능한 시간들을 찾고 최대 값을 확인하면 될거 같다. 이 생각을 하니까 시뮬레이션 돌리는 시간보다 답을 찾아 보고 확인하는 시간이 훨씬 빨랐다는게 신기했다.

 

전체 진행 시간 / 각 심사 위원이 한명 처리 시간 == "각 심사 위원이 처리하는 사람수"

 

"각 심사 위원이 처리하는 사람수"가 n보다 크면 right = mid-1

"각 심사 위원이 처리하는 사람수"가 n보다 작으면 left = mid+1

 

음 그런데 틀렸다.

 

이분 탐색은 좌우 값이 중요한거 같다. 좌는 0으로 했고, 우는 그냥 내가 생각하는 최대값으로 했다가 다시 1000000000 실제 가능한 최대값으로 바꾸니까 점수가 올라감. 44점이다 근데 왜 틀린 거지 ㅋㅋ

 

#include <string>
#include <vector>

using namespace std;

int getAvailPersonN(vector<int>&times, int totalTime) {
	int n = 0;
	for (int i = 0; i < times.size(); i++) {
		n += totalTime / times[i];
	}
	return n;
}

int BinarySearch(vector<int>&times, int n) {
	int left, right, maxv = 0;
	left = 0;

	for (int i = 0; i < times.size(); i++) {
		if (times[i] > maxv) {
			maxv = times[i];
		}
	}
	right = 1000000000;
	int minv = right;

	while (left <= right) {
		int mid = (left + right) / 2;

		int avail = getAvailPersonN(times, mid);

		if (minv > mid && avail >= n) {
			minv = mid;
		}

		if (avail < n) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return minv;
}

long long solution(int n, vector<int> times) {
	long long answer = 0;

	answer = BinarySearch(times, n);

	return answer;
}

int main() {
	vector<int> tmp;
	tmp.push_back(7);
	tmp.push_back(10);
	solution(6, tmp);

	return 0;
}