C++ set 과 unordered_map - 백준 알고리즘 오답노트 10816

백준 BOJ 알고리즘 오답노트 - 10816 번

의문점:

//?. Set 은 로그n 의 count을 가지는것이 아닌가? 아니래..

 

 

//FB1. set의 count는 

 

//Time Complexity = Logarithmic in size and linear in the number of matches.

//    시간복잡도 N -> O(NM) -> 500,000 * 500,000 = 250,000,000,000

//FB2. 좀더 빠른 자료구조인 map을 사용 더 빠른 C++11 의 unordered_map을 사용 정렬되지 않는 map

 

//FB3. map.count 는 0또는 1을 반환 -> 존재 여부 확인

//       map[3] 은 키값에 해당하는 value을 반환하고 , 키가 없다면 키를 생성하고 value을 초기값으로 매칭

1. Set은 red black tree로 만들어져 삽입 탐색이 lgN 복잡도를 가진다고 배웠다.

하지만 count는 시간복잡도가 N이 었다. 

2. 정렬이 필요없는 map은 C++11의 unordered_map을 이용하면 속도향상에 도움이 된다.

3. map에서 key에대한 value가 존재하는지 확인하는 방법

map.count(key 값) != 0 

map[key값] 은 키값에 해당하는 value을 반환하고 , 키가 없다면 키를 생성하고 value을 초기값으로 매칭

//10816 // 재성공
 
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    int cases1; cin>> cases1; multiset<int> card;
    while(cases1--){ int val; cin>>val; card.insert(val);}
    int cases2; cin>>cases2;
    while(cases2--){ int val; cin>>val; cout<< card.count(val)<<" ";}
    return 0;
}
 
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
int main(){
        int cases1; 
        scanf("%d",&cases1);
        multiset<int> card;
        while(cases1--){ int val; scanf("%d",&val); card.insert(val);}
        int cases2; 
        scanf("%d",&cases2);
        while(cases2--){
            int val; scanf("%d",&val);
            printf("%d ",card.count(val));
        }
    
}
 
 
#include<cstdio>
#include<unordered_map>
#include<set>
#include<algorithm>
using namespace std;
int main(){
        
        // unordered_map<int,int> map;
        // map[0] = 1; map[2] = 2;
        // printf("%d %d %d\n",map.count(0),map.count(1),map.count(2));
        // printf("%d %d %d\n",map[0],map[1],map[2]);
        // printf("%d %d %d\n",map.count(0),map.count(1),map.count(2));
        int cases1; 
        scanf("%d",&cases1);
 
        unordered_map<int,int> card;
        while(cases1--)
        { 
            
            int val; scanf("%d",&val); 
            if(card.count(val)){
                card[val] = card[val]+1;
            }
            else{
                card[val] = 1;
            }            
 
        }
    
        int cases2; 
        scanf("%d",&cases2);
        while(cases2--){
            int val; scanf("%d",&val);
            printf("%d ", card[val] );
        }
    
}