[C언어 / 백준 - 10816] 숫자 카드2 / lower_bound, Upper_bound

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1 복사

10

6 3 2 10 10 10 -10 -10 7 3

8

10 9 -5 2 3 4 5 -10

예제 출력 1 복사

3 0 0 1 2 0 0 2

 

 

현재 가지고 있는 카드 중에서 입력한 카드가 몇개 존재하는지 출력하는 문제.

당연히 완전탐색으로는 시간초과가 날거라고 예상해 이분탐색으로 해결하려했지만 똑같이 시간초과가 나서 구글링을 했던 문제이다. 전까지는 몰랐던 lower_bound와 Upper_bound를 이용하여 해결하는 문제라는 걸 알게 되었고, 이 부분에 대해 공부할 수 있던 문제이다.

 

lower_bound / Upper_bound는 이분탐색을 응용한 알고리즘으로,

* 이분탐색은 정렬된 수를 분할하여 찾고자 하는 k값의 index를 찾는 알고리즘 이라고 하면,

1) lower_bound는 정렬된 수들 중 찾고자 하는 k 이상의 최초값 index를 찾는 알고리즘이고,

2) Upper_bound는 정렬된 수들 중 찾고자 하는 k를 초과한 최초값의 index를 찾는 알고리즘이다. 

 

lower bound는 '원하는 값 k 이상이 처음 나오는 위치를 찾는 과정
Upper bound는 '원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 과정

lower bound를 구현하는 건 이분탐색고 거의 똑같다.
약간의 차이가 있다면 일치하는 값이 아닌 
이상의 값을 찾는 것이기 때문에 일치하는 값이 존재하지 않을 수 있다

<lower_bound 소스 코드>
int lower_bound ( int arr[], int key, int size) { 
	int start = 0;
	int end = size-1;

	while(start < end){
		int mid = (start+end) / 2;
		
		if(arr[mid] <= key)
			end = mid;
		else
			start = mid+1;
	}
	return end;
}


Upper bound는 이상의 값이 아닌 '초과'의 값이기 때문에 
이것만 신경써서 약간의 코드만 수정해주면 된다.

<Upper_bound 소스 코드>
int Upper_bound ( int arr[], int key, int size){
	int start = 0;
	int end = size-1;

	while(start < end){
		mid = (start + end) / 2;

		if (key < arr[mid]){
			end = mid;
		}
		else{
			start = mid+1;
		}
	}
	return end;
}

lower_bound / Upper_bound를 이용하면 이 문제를 풀 수 있다.

하지만 위의 코드 그대로 lower/Upper_bound를 구현하여 이 문제를 해결하려 한다면 정답을 받을 수 없다.

왜냐하면 예외의 경우가 존재하고 그런 경우들까지도 해결해줘야하기 때문이다.

 

예시로, 10816문제의 가지고 있는 카드를 정렬하게 되면

-10 -10 2 3 3 6 7 10 10 10

이 된다. 이걸 upper를 하게 되면 upper의 반환값은 9가 되고 lower의 반환갑은 7이 되어 (9-7)=2로 출력하게 된다. 소스코드상 오류는 없지만 upper의 정의가 초과한 최초의 값 인덱스이기 때문에 위 예제의 10의 반환값인 9는 초과한 값의 인덱스가 아닌 동일한 10의 index를 반환하게 오류를 범하게 되는 것이다. 이 부분만 약간 수정해주면 정답을 받을 수 있는 문제이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define MAX_SIZE 500001

int N, M;
int have[MAX_SIZE];
int want[MAX_SIZE];

int lower_bound(int* have, int key, int size) {
	int mid;
	int start = 0, end = size - 1;

	while (start < end) {
		mid = (start + end) / 2;
		if (key <= have[mid])
			end = mid;
		else
			start = mid + 1;
	}
	return end;
}

int Upper_bound(int* have, int key, int size) {
	int mid;
	int start = 0, end = size - 1;

	while (start < end) {
		mid = (start + end) / 2;
		if (key < have[mid])
			end = mid;
		else
			start = mid + 1;
	}
	if (have[end] == key) {
		return end + 1;
	}
	return end;
}

int cmp(const void* lhs, const void* rhs) {
	if (*(int*)lhs > *(int*)rhs) {
		return 1;
	}
	else {
		return -1;
	}
}

void Solve() {
	int lower;
	int upper;
	
	for (int i = 0; i < M; i++) {
		lower = lower_bound(have, want[i], N);
		upper = Upper_bound(have, want[i], N);
		printf("%d ", upper-lower);
	}
}

void Input_Have() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &have[i]);
	}
}

void Input_Want() {
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d", &want[i]);
	}
}

int main() {
	Input_Have();
	Input_Want();
    
	qsort(have, N, sizeof(int), cmp);
	
	Solve();
    
	return 0;
}