반응형
백준 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을 초기값으로 매칭
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | //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] ); } } | cs |
반응형
'알고리즘 > 백준[BOJ] 오답노트' 카테고리의 다른 글
C++cin/cout 시간초과 해결 - 백준 알고리즘 오답노트 10815 (0) | 2019.02.02 |
---|---|
C++ stack 활용 애디터 - 백준 알고리즘 오답노트 1406 (0) | 2019.02.02 |
C++ scanf의 리턴값 활용 - 백준 알고리즘 오답노트 10951 (0) | 2019.02.02 |
C++ 큐활용 문제 - 백준 알고리즘 오답노트 2346 (0) | 2019.02.02 |
C++ \랑" 출력하기 - 백준 BOJ 알고리즘 오답노트 - 10172 번 (0) | 2019.02.02 |