대엉코딩

www.acmicpc.net/problem/2776

1. 풀이방법

- 시간제한은 2초 

- N,M 모두 최대 1,000,000 이므로 M배열의 각각의 원소에 대해 N배열을 선형탐색하면 시간초과가 발생

- N배열을 정렬하고 (c++ stl에서 제공하는 sort함수는 O(nlogn)을 보장해줍니다.

- 그후 M배열 각각의 원소로 N배열에 대해서 이분탐색을 진행 하시면 됩니다.

- 재귀, 반복문 다 구현 가능하며 저는 이 문제는 while문으로 구현하였습니다.

2. 주의사항

- 시간초과

3. 나의코드

#include<bits/stdc++.h>
using namespace std;



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t, n, m;
	cin >> t;
	while (t--) {
		cin >> n;
		vector<int> narr(n);
		for (int i = 0; i < n; i++) cin >> narr[i];
		sort(narr.begin(), narr.end()); // 정렬

		cin >> m;
		vector<int> marr(m);
		for (int i = 0; i < m; i++) cin >> marr[i];

		for (int i = 0; i < m; i++) { //수첩 2
			int lowindex = 0; int highindex = n - 1;
			while (1) {
				if (lowindex > highindex) { cout << 0<<"\n"; break;}
				int midindex = (lowindex + highindex) / 2;
				if (narr[midindex] == marr[i]) {cout << 1 << "\n"; break;}

				if (narr[midindex] > marr[i]) {
					highindex = midindex - 1;
				}
				else {
					lowindex = midindex + 1;
				}
			}
		}
	}
	return 0;
}

www.acmicpc.net/problem/2792

1. 풀이방법

- 구현 문제를 많이 풀다보니 이런문제를 처음 봤을 때, 조금 당황스러웠습니다...;

- 어쨋든 최소질투심을 유발하게끔 나눠주는 방법은 1과 최대보석의 수 중에 있을 것이니까

- 이분 탐색을 통해 그것을 탐색해가면서 mid의 값이 아이들에게 조건에 맞게 나누어 줄 수 있는지 확인.

- 나누어 줄 수 있으면 더 작은 질투심을 유발할 수 있는 값이 있는지 mid보다 작은 쪽을 탐색.

- 아니라면 mid보다 큰 쪽을 탐색.

- 최소값을 출력하여 주었습니다.

2. 주의사항

- 없음.

3. 나의코드

#include<bits/stdc++.h> 
using namespace std;

long long n, m;
long long numarr[300001];
long long result = 1e18;

bool canspread(long long mid) {
    long long num = 0;
    for (int i = 0; i < m; i++) {
        num += numarr[i] / mid;
        if (numarr[i] % mid) num++;
    }
    return n >= num;
}
int main() {
    cin >> n >> m;
    long long left = 1; long long right = 0;
    for (int i = 0; i < m; i++) {
        cin >> numarr[i];
        if (right < numarr[i]) right = numarr[i];
        }
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (canspread(mid)) {
            if (result > mid) result = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    cout << result << "\n";
    return 0;
}

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;
}