[백준] [C/C++] [★] 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

알고리즘 [ 접근 방법 ]

정렬 + 이분탐색 문제이다.

백준 10815번 : 숫자 카드 문제를 풀고 바로 풀어보았다. 앞선 숫자 카드 문제와 거의 동일한 방식으로 먼저 풀어보고 코드를 일부만 수정해서 풀이 해봤다.

기존문제는 단순히 카드를 가지고 있는지 아닌지 유무만 판단하면 됐지만, 이번 문제는 카드를 가지고 있다면 몇개가지고 있는지 까지 판단할 필요가 있었다.

처음에는 이분 탐색으로 카드를 나눈뒤에 카드를 가지고 있는게 확인 된다면 인덱스값에 +1 혹은 -1을 반복해서 적용한 뒤 몇장의 카드를 가지고 있는지 확인할 수 있게 해봤는데 시간 초과가 발생했다.

주어진 조건이 카드가 최대 500,000장 까지 존재할 수 있어서 이중 반복문을 사용한다면 O(N^2)의 시간복잡도가 발생하기 때문인것 같다.

결국 레퍼런스를 참고했더니 새로운 컨테이너를 사용해서 푸는 문제였다.

lower_bound

• 찾으려는 key 값보다 같거나 큰 숫자가 배열 혹은 벡터의 몇 번째에서 처음 등장하는지 찾기 위함
• 사용 조건 : 배열 혹은 벡터가 오름차순 정렬 되어있어야함.
• 반환 : 처음 등장한 위치의 인덱스값을 반환한다
• 배열 : lower_bound(arr,arr+n,k) (n : 찾으려는 배열크기, k : 찾으려는 숫자)
• 벡터 : lower_bound(arr.begin(),arr.end(),k)

upper_bound

• 찾으려는 key값을 초과하는 숫자가 몇번째에서 처음 등장하는지 찾기 위함
• 사용 조건 : 배열 혹은 벡터가 오름차순 정렬 되어있어야함.
• 반환 : key를 처음으로 초과하는 숫자가 나오는 위치의 인덱스 값을 반환한다.
• • 배열 : upper_bound(arr,arr+n,k) (n : 찾으려는 배열크기, k : 찾으려는 숫자)
• 벡터 : upper_bound(arr.begin(),arr.end(),k)

풀이 (시간초과)

#include <iostream>
#include <algorithm>
#define MAX 500000

using namespace std;

int n, m;
int num[MAX + 1];
int check[MAX + 1];
int res[MAX + 1];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> check[i];
	}

	sort(num, num + n);

	for (int i = 0; i < m; i++) {
		int left = 0;
		int right = n - 1;
		int mid = (left + right) / 2;
		while (left <= right) {
			if (check[i] == num[mid]) {
				res[i]++;
				int temp = mid;
				while (1) {
					if (check[i] == num[temp+1]) {
						res[i]++;
						temp++;
					}
					else break;
				}
				temp = mid;
				while (1) {
					if (check[i] == num[temp-1]) {
						res[i]++;
						temp--;
					}
					else break;
				}
				break;
			}
			else if (check[i] > num[mid]) {
				left = mid + 1;
				mid = (left + right) / 2;
			}
			else if (check[i] < num[mid]) {
				right = mid - 1;
				mid = (left + right) / 2;
			}
		}
	}

	for (int i = 0; i < m; i++) cout << res[i] << " ";
}

풀이

#include <iostream>
#include <algorithm>
#define MAX 500000
using namespace std;

int n, m;
int num[MAX + 1];
int check[MAX + 1];
int res[MAX + 1];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> check[i];
	}

	sort(num, num + n);

	for (int i = 0; i < m; i++) {
		auto u = upper_bound(num, num + n, check[i]);
		auto l = lower_bound(num, num + n, check[i]);
		res[i] = u - l;
	}

	for (int i = 0; i < m; i++) {
		cout << res[i] << " ";
	}
}