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

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

10816번: 숫자 카드 2

 

 

 

 

 

 

 

---

 

일단 그냥 전체를 도는 반복문으로 출력을 해봤다

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


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	int numN;
	vector<int> ns;
	for (int i = 0; i < n; i++)
	{
		cin >> numN;
		ns.push_back(numN);
	}

	int m;
	cin >> m;

	int numM;
	vector<int> ms;
	for (int i = 0; i < m; i++)
	{
		cin >> numM;
		ms.push_back(numM);
	}

	///////////////////////////////////// 출력

	int cnt = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (ns[j] == ms[i])
				cnt++;
		}

		cout << cnt << " ";
		cnt = 0;
	}
}

 

 

 

즉, 선형 탐색법을 이용한 것인데 역시나 시간 초과가 나온다

 

더 빠르게 탐색할 방법이 필요하다

 

일단 어찌되었건간에 우리는 카드 하나를 찾았다고 끝내는게 아니라

상근이가 가지고 있는 모든 카드를 들여다봐야한다 몇 개를 가지고 있는지 알아야하기 때문이다

 

그래서 다음으로는 이진탐색법을 생각해본다

일단 상근이의 카드를 정렬해야하고

찾아야할 카드가 중간값보다 작은지 큰지 같은지 검사하고

그 값이 몇개가 있는지 세어야한다

 

코드로 구현 후 해보았지만 여전히 시간초과다 ㅠㅠ 

그래서 다른 방법을 이용해야겠다 하고 다시 생각해봤다

 

이전 문제에서 풀었던 맵을 이용할 방법은 없을까 ? 라고 생각해봤다

결과는 성공이었다

 

 

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


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	map<int, int> nums;
	
	int numN;
	for (int i = 0; i < n; i++)
	{
		cin >> numN;
		nums[numN]++;
	}

	int m;
	cin >> m;

	int numM;
	for (int i = 0; i < m; i++)
	{
		cin >> numM;

		map<int, int>::iterator it = nums.find(numM);

		if (it != nums.end())
			cout << it->second << " ";
		else
			cout << "0" << " ";
	}
}

 

상근이의 카드를 입력받을 때 

순서대로 그냥 입력받는게 아니라 상근이 카드의 정수값을 맵의 key값으로 넣어주고 

그 키값이 불릴때마다 value값을 증가시켜주는 방법이다

 

만약 상근이의 카드가 10이라면 

map[10] = 1 이 되는거고

10이 한 장 더 있었다면 

map[10] ++ 해서 map[10] = 2가 되는 것이다!

그리고 상근이에게 없는 카드라면 0이 나오게 된다

 

탐색하는 방법을 사용하면 

탐색할 상근이의 카드 수 X 탐색하는 숫자의 카드 수 가 되지만

이렇게 맵에 카운트를 저장하는 방법을 사용하면

탐색하는 숫자의 카드 수만 신경쓰면 된다

 

이 방식으로 탐색을 빨리 해야지 ! 보다는 

저장할 때 목적을 가지고 카운트를 저장을 해버리니 원하는 결과를 찾기 쉬웠다