백준 10816 숫자 카드 2

문제 : https://www.acmicpc.net/problem/10816

 

서론

일반적인 이분탐색을 한 후 목표값을 찾았을때 목표값의 좌우로 반복 or 재귀로 목표값과 같은 값이 있는지 탐색하는 코드를 짰는데 시간초과가 난다.

결국 검색을 했는데, 나와 유사한 다른분의 코드(이분탐색 후 같은게 있는지 검색하는 방식)도 돌려봤더니 마찬가지로 시간초과가 나온다

아마도 특정 시점에서 시간복잡도를 엄밀하게 하는 데이터가 추가된 것 같다.

 

풀이

검색 결과 upper_bound, lower_bound라는 키워드를 얻었다.

처음보는거라 공부해야했는데

https://blog.naver.com/bestmaker0290/220820005454

이곳을 참조하여 lower_bound, upper_bound를 만든 후

upper_bound - lower_bound 해주었다.

 

구현

//c++

#pragma warning(disable : 4996)
#include <cstdio>
#include <iostream>
#include <algorithm>

int card[500001];
int n, m;

int lower_bound(int start, int end, int target) {
	
	while (start != end) {
		//std::cout << start << " " << end << std::endl;

		int mid = (start + end) / 2;
		if (card[mid] < target) start = mid + 1;
		else end = mid;
	}
	return start;
}

int upper_bound(int start, int end, int target) {

	while (start != end) {
		//std::cout << start << " " << end << std::endl;

		int mid = (start + end) / 2;
		if (card[mid] <= target) start = mid+1;
		else end = mid;
	}
	return start;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &card[i]);
	}
	std::sort(card, card + n);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		int start = lower_bound(0, n, x);
		int end = upper_bound(0, n, x);
		//printf("%d ", start);
		//printf("%d ", end );
		printf("%d ", end - start);
	}
}

 

시간초과1

//c++

#pragma warning(disable : 4996)
#include <cstdio>
#include <iostream>
#include <algorithm>

int card[500001];
int n, m;

int search(int target) {
	int sum = 0;
	int start = 0;
	int end = n - 1;

	while (1) {
		int mid = (start + end) / 2;
		//std::cout << mid << std::endl;
		if (target == card[mid]) {
			sum++;
			int cnt = 1;
			while (1) {
				if (card[mid + cnt] != target && card[mid - cnt] != target) break;
				if (card[mid + cnt] == target) sum++;
				if (card[mid - cnt] == target) sum++;
				cnt++;
			}
			break;
		}
		else if (target > card[mid]) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
		if (start > end) return 0;
	}
	return sum;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &card[i]);
	}
	std::sort(card, card + n);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		printf("%d ", search(x));
	}
}

 

시간초과2

//c++

#pragma warning(disable : 4996)
#include <cstdio>
#include <iostream>
#include <algorithm>

int card[500001];
int n, m;

int search(int target, int start, int end) {
	if (start > end) return 0;
	//std::cout << start << " " << end << std::endl;

	int sum = 0;
	int mid = (start + end) / 2;

	if (target == card[mid]) {
		return search(target, start, mid - 1) + search(target, mid + 1, end) + 1;
	}
	else if (target > card[mid]) {
		return search(target, mid + 1, end);
	}
	else {
		return search(target, start, mid - 1);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &card[i]);
	}
	std::sort(card, card + n);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		printf("%d ", search(x, 0, n-1));
	}
}