[백준] 10816번 숫자 카드2
[백준] 10816번 숫자 카드2
문제 링크: https://www.acmicpc.net/problem/10816
문제 및 입출력
문제 접근
처음에 이진 탐색도 생각이 났고, 해쉬를 써서 하는 법도 생각이 났다. 해쉬 함수를 사용하여, O(1)의 시간으로 값을 find할 수 있다는 생각에, hash_map을 사용하여 구현하였다.
먼저 입력들을 받고, target 숫자들을 해쉬에 넣어준 후에, 상근이가 가지고 있는 값들을 해쉬에 키로 가지고 있는지 여부를 판단 후, 만약 가지고 있지 않는다면, 넘어가고 가지고 있다면, key에 대한 value를 +1해주었다.
결국 시간 복잡도는 O(N)일거 같다. 왜냐면, 해쉬 맵에서 찾는데 걸리는 시간은 O(1)이지만, N개의 값들을 찾아야되기 때문에,,
코드 구현
#include <iostream>
#include <unordered_map>
using namespace std;
int target[500001];
int sanggeon[500001];
int targetNum, haveNum;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
unordered_map<int, int> hashMap;
cin >> haveNum;
for(int i = 0 ; i < haveNum ; i++){
cin >> sanggeon[i] ;
}
cin >> targetNum;
for(int i = 0 ; i < targetNum ; i++){
cin >> target[i];
hashMap[target[i]] = 0;
}
for(int i = 0 ; i < haveNum ; i++){
auto it = hashMap.find(sanggeon[i]);
if(it != hashMap.end()){
it->second = it->second + 1;
}
}
for(int i = 0 ; i < targetNum ; i++){
auto it = hashMap.find(target[i]);
cout << it->second << " ";
}
}
평가
오랜만에 다시 알고리즘 문제를 푸니 재미있다,,,,ㅎㅎ
Author And Source
이 문제에 관하여([백준] 10816번 숫자 카드2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpg0518/백준-10816번-숫자-카드2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)