대엉코딩

www.acmicpc.net/problem/1620

1. 풀이방법

- 포켓몬도감을 입력받아 찾으면 되는 문제입니다.

- 첫번쨰 문제는 입력이 숫자 일수도, 포켓몬 이름 일수도 있다는 것입니다.

- 이름의 경우 알파벳만으로 이루어져있다고 했으므로, 입력받은 문자열의 첫글자가 알파벳인지 숫자인지만

- 구분해서 구하여주었습니다.

2. 주의사항

- 처음에 그냥 선형탐색으로 짰는데, 이 경우 최대연산 수가 대략 10,000,000,000이 되므로 시간조건을 만족x

- 결국 이분탐색을 이용하고자 하였고 그러려면 알파벳순으로 정렬을 해야 하는데 , 그러면

- index가 섞이기 때문에 따로 알파벳입력이 들어왔을 떄를 위한 index도 가지고 있는 배열을 선언하였습니다.

- 숫자가 들어올 경우 vector<string> 을 통해 index를 구해서 바로 접근 하였고,

- 알파벳으로 들어올 경우 vector<pair<string,int>> 를 정렬해놓은 것을 통해 이분 탐색으로 찾았습니다.

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;

vector<string> dokam;
vector<pair<string, int>> dokamname; //알파벳이 입력되었을 경우 이분탐색을 위한 !
string tmps;
void find(int bot, int top) {
	if(bot>top) return;
	int mid = (bot + top) / 2;
	if (tmps == dokamname[mid].first) { cout << dokamname[mid].second << '\n'; return; }
	else if (tmps < dokamname[mid].first) { find(bot, mid - 1); }
	else { find(mid + 1, top); }
}
bool compare(pair<string, int> &a, pair<string, int> &b) {
	if (a.first < b.first) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		dokam.emplace_back(s);
		dokamname.push_back({ s,i });
	}
	sort(dokamname.begin(), dokamname.end(), compare);
	while (m--) {
		int result = 0;
		cin >> tmps;
		if (tmps[0] >= '0'&&tmps[0] <= '9') { //숫자일경우
			int deci = 1;
			for (int i = tmps.length() - 1; i >= 0; i--) {
				result += deci * (int)(tmps[i] - '0');
				deci *= 10;
			}
			cout << dokam[result-1] << "\n";
		}
		else { //선형탐색으로는 시간초과 -> 이분탐색 진행
			find(0,n-1);
		}
	}

	return 0;
}

www.acmicpc.net/problem/10815

1. 풀이방법

- 일단 문제 input사이즈를 보면 크다 500,000

- 만약 두번의 for문을 돌려서 탐색을 할경우 최악의경우 250,000,000,000 인데, 

- c++기준 대략 1초에 1억번의 연산을 한다고 가정하여도, 시간제한 2초를 훨씬 넘기 때문에 

- 선형탐색을 사용해서는 안된다 ----->이진탐색(binary search)를 사용하자.

- 오름차순으로 sorting을 한 후 시작한다.

2.주의사항

- 전형적인 이진탐색문제로서 이론을 그대로 코드로 옮겨주면 되겠다.

- 조건을 살짝씩 빼먹을 경우 무한루프에 자주 빠지니 조건을 꼼꼼하게 체크 해주자....>!

3. 나의코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M;
int Narr[500001];
int Marr[500001];

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> Marr[i];
	}
}
void bs(int start,int end,int searchnum) {
	int mid = (start + end) / 2;
	if (Narr[mid] == searchnum) { cout << 1 << " "; return; }
	if (mid >= end) { cout << 0 << " "; return; }
	if (Narr[mid] > searchnum) { bs(start, mid-1, searchnum); }
	if (Narr[mid] < searchnum) { bs(mid+1, end, searchnum); }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	sort(Narr, Narr+N);
	for (int i = 0; i < M; i++) {
		bs(0, N - 1, Marr[i]);
	}
	return 0;
}

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

그냥 모든 경우의 수를 입력 받은 후 (듣지 못하는 사람) 을 보지 못하는 사람을 입력받을 때 

듣지 못하는 사람 전체와 비교를 하면 시간 초과가 뜹니다 (n,m이 무려 500,000이기 때문에 )

그래서 오랜만에 binarysearch를 직접 구현하여 문제를 해결 하였습니다.

그리고 문제에서 사전 순 배열을 원하였으므로 중간에 sort를 사용하시면 됩니다.