C++) 백준 10816번: 숫자 카드 2

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

10816번: 숫자 카드 2

음.. 사실 이거 굳이 포스팅 하려고 하지는 않았는데.. (너무 쉽게 풀려서) 구글링을 해보니 다들 이진탐색으로 풀어서 '뭐지?' 싶어서 더 쉽게 풀고 싶은 다른 사람들에게 도움이 될까 하여 적는다.

 

< 풀이 방법 1 - map STL 이용(시간 초과) >

처음에는 map<int, int>를 선언하여 찾았다. 근데 사실 시작 전부터 안될 것 같긴 했다 ㅋㅋㅋ.. value가 같은 게 몇 개 있는지를 찾아야 하기 때문에 반복자 for문을 돌려야 해서 이중반복문이 되어버리는 것. 그래도 한 번 해보기로 했는데 역시나 시간 초과.

 

< 풀이 방법 2 - 배열 이용(성공) >

배열로 처음에 20000001만큼 크기를 선언해주고 -10000000 ~ 10000000의 인덱스들을 그대로 옮겼다(배열은 음수의 인덱스를 가질 수 없으니까).  따로 더 설명은 필요 없을 듯. 이거 혹시 맵으로 푼 사람이 있나 싶어서 구글링 해봤는데 웬 이진탐색만 나와서... 이게 훨씬 쉬우니 도움이 되었으면 좋겠음.

 

아래는 코드이다.

 

#include <iostream>
#include <algorithm>

#define default 10000000

using namespace std;

int arr[20000001];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int N, M;
cin >> N;
int num;
for (int i = 0; i < N; i++) {
cin >> num;
arr[num + default]++;
}

cin >> M;
for (int i = 0; i < M; i++) {
cin >> num;
cout << arr[num + default] << " ";
}

return 0;
}