[백준 10816번] 숫자 카드 2 ( map / 이분탐색(upper,lowerbound) )

캡쳐한게 깨져서 올라가길레 그냥 링크 걸었습니다.

나중에 이분탐색으로 다시 풀어보기

10816번: 숫자 카드 2

#include <bits/stdc++.h>

using namespace std;
map<int, int> m;
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
	int N,M;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;
		m[temp]++;
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int temp;
		cin >> temp;
		if (m.find(temp) != m.end())
		{
			cout << m[temp] << " ";
		}
		else {
			cout << "0" << " ";
		}
	}


}

---

#include <bits/stdc++.h>

using namespace std;
int ary[500001];
int N, M;

//upperbound : left위치가 최대 index
//lowerbound : right위치가 최소 index
//upper-lower +1 : 해당 target의 개수.
int upperbound(int target) {
	int left = 0, right = N - 1, mid;
	while(left <= right)
	{ 
		mid = left + (right - left) / 2;
		if (target >= ary[mid]) left = mid + 1; 
		else {
			right = mid - 1;
		}
	}
	return right;
}
// upper와 lower의 부등호에 유의할것. 구현할 때 주의사항임.
// " 같을 때 어떻게 처리할 것이냐."
// 기억하기 편하려면 upper는 right가 index를 찾고, lower는 left가 index를 찾으니.
// index찾는 쪽에는 등호를 쓰지 않는다. 로 암기해도 좋을 것 같다.
// 물론 알고리즘을 이해하는게 제일 낫다.
int lowerbound(int target) {
	int left = 0, right = N - 1, mid;
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (target > ary[mid])
			left = mid + 1;
		else {
			right = mid - 1;
		}
	}
	return left;
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;
		ary[i] = temp;
	}
	sort(ary, ary + N);
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int temp;
		cin >> temp;
		int upper = upperbound(temp);
		int lower =lowerbound(temp);
		if (upper < lower) cout << "0" << " ";
		else {
			cout << upper - lower + 1 << " ";
		}
		
	}


}

이분탐색 ( upperbound, lowerbound )

이분탐색을 조금 변형하면

122334567777 이런식으로 배열이 있을 때 특정 값의 최대 index와 최소 index를 얻을 수 있다.

코드 구현의 부등호를 주의하자.

 

[백준/10816] 숫자 카드 2 (이분 탐색)

이해는 여기에서 했으니 까먹었다면 위 링크를 참조하자.

 

성능 비교해보니 코드 길이는 길지만 메모리 /시간 면에서 절반이상 효과가 좋다.

map을 써도 통과는 했었지만, 이분탐색을 활용하는 것은 코딩테스트때 효율성문제(특히 카카오)로 나올 수 있으니 활용법이 있다면 정리를 틈틈히 하자.