[C++] 백준 14단계 - 10816번 문제 (숫자 카드 2)

문제설명

 

소스코드

#include <iostream>
#include <map>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(false); //표준 스트림 동기화 해제
	cin.tie(nullptr); //입출력 연결 끊기
	map<int, int> m;
	int N, M;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int input;
		cin >> input;
		++m[input];
	}
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int input;
		cin >> input;
		cout << m[input] << " ";
	}
}

 

설명

• 표준 스트림 동기화해제, 입출력 연결 끊기 -> 시간초과 방지
• 선형 방식인 이중for문은 시간복잡도 O(N^2)이므로 시간초과가 발생한다.
• map 라이브러리의 map을 사용하면 시간복잡도O(log(N))이라서 시간초과가 발생하지 않는다.