백준 10816번 숫자 카드 2

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

 

아이디어:

1. map 사용. map의 first는 카드, second는 갯수로 활용. ex) <10, 2장>, <11, 0장>, <12, 3장> ...

2. 출력은 그냥 map의 second 출력

 

#include <iostream>
#include <map>

using namespace std;

map <int, int> card;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m, k;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> k;
		card[k]++;
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> k;
		cout << card[k] << " ";
	}

	return 0;
}

 

틀린 코드 설명:

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m, k;

	cin >> n;
	int* N = new int[n];

	for (int i = 0; i < n; i++) {
		cin >> k;
		N[i] = k;
	}

	cin >> m;
	int* M = new int[m];

	for (int i = 0; i < m; i++) {
		cin >> k;
		M[i] = k;
	}

	for (int i = 0; i < m; i++) {
		cout << count(N, N + n, M[i]) << " ";
	}

	return 0;
}

 

원인(추정): count 함수로 인한 시간 초과

 

다른 방식:

이분 방식

int형 1차원 배열에 카드를 입력하고 오름차순으로 정렬한다.

찾는 숫자가 처음 나오는 위치, 찾는 숫자보다 큰 값이 처음 나오는 위치를 구하고 뺄셈으로 개수 구해서 출력한다.

upper_bound(), lower_bound() 함수를 사용