[백준 BOJ] 10816 숫자 카드 2 C++

백준 10816번: 숫자 카드 2

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

10816번: 숫자 카드 2

---

문제

예제

• 문제해석 및 풀이

 이 문제는 제시되는 숫자 카드들이 상근이가 몇 개를 들고 있는지를 구현하면 되는 문제이다. 입력은 차례대로 상근이가 들고 있는 카드의 개수, 카드의 수(중복이 가능함), 맞춰야 하는 카드의 개수, 카드의 수 (중복이 가능함)를 받는다. 숫자가 몇 개가 있는지 탐색하기 용이한 lower_bound와 upper_bound를 활용하면 쉽게 구현할 수 있다.

• 코드

 

#include <iostream>
#include <algorithm>
using namespace std;

int sangeun[500000];
int guess[500000];
int answer[500000] = { 0, };

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> sangeun[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> guess[i];
	}
	sort(sangeun, sangeun + n);
	for (int i = 0; i < m; i++) {
		answer[i] = upper_bound(sangeun, sangeun + n, guess[i])
        	- lower_bound(sangeun, sangeun + n, guess[i]);
	}
	for (int i = 0; i < m; i++) {
		cout << answer[i] << " ";
	}
	return 0;
}

 upper_bound와 lower_bound는 이진 탐색을 기반으로 하는 c++에서 제공하는 함수이다. 따라서 이 함수들의 시간복잡도는 O(logN)이다. 다만 이 함수를 사용하기 위해서는 대상 배열이 오름차순으로 정렬이 되어 있어야 한다. 따라서 sort로 정렬을 시켜주었다. upper_bound는 찾으려고 하는 값을 초과하는 값이 나오는 위치의 인덱스 값을 리턴하고 lower_bound는 찾으려고 하는 값 이상의 값이 나오는 위치의 인덱스 값을 리턴한다. 따라서 이 둘을 빼면 찾으려는 값의 개수를 구할 수 있게 되는 것이다.

• 정리

 이 문제를 통해 c++에서 lower, upper_bound를 지원한다는 것을 배울 수 있었고 앞으로 정렬이 가능하며 원하는 값의 개수를 묻는 문제가 있다면 이를 적용해 풀 수 있을 것이다.

 궁금한 것이나 더 나은 코드 및 방법, 그리고 잘못된 것이 있다면 댓글에 남겨주시기 바란다.