BOJ 10816번 :: 숫자 카드 2

#문제

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

10816번: 숫자 카드 2

 

#작성 코드

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

#include <iostream> #include <vector> #include <algorithm> using namespace std;   int n, m; vector<pair<int, int> > card;   int bsearch(int x){     int start = 0;     int end = card.size();     int mid;     while( start <= end ){         mid = (start+end)/2;         if( card[mid].first < x){             start = mid+1;         }         else if( card[mid].first > x){             end = mid-1;         }         else{             // card[mid].first==x             return card[mid].second;          }     }     // x가 쓰여진 카드를 찾을 수 없을때     return 0;  }   int main(){     scanf("%d", &n);     vector<int> nums;     for(int num=0; num<n; num++){         int x;         scanf("%d", &x);         nums.push_back(x);     }     // 가지고있는 카드들 카드에 적힌 수 기준으로 오름차순정렬      sort(nums.begin(), nums.end());          // 입력받은 카드들 다시 벡터에 넣으면서 개수 저장.      card.push_back(make_pair(nums[0],1));     int index =0;     for(int i=1; i<n; i++){         if( nums[i]==card[index].first){             card[index].second++;         }         else{             card.push_back(make_pair(nums[i], 1));             index++;         }     }     scanf("%d", &m);     for(int i=0; i<m; i++){         int x;         scanf("%d", &x);         printf("%d ", bsearch(x));     }      return 0;  }  Colored by Color Scripter

cs

##

처음에 n개의 카드에 적힌 숫자들을 입력받으면서

vector<pair<int, int> > 를 사이즈만큼 순회하면서 같은 숫자가 적힌 카드가 있다면 카드 개수를 1 늘리고, 그런 카드가 없다면 {카드에 적힌 숫자, 1}을 push하는 방식으로 코드를 작성했는데, 시간초과가 발생했다.

 

중복에 관계없이 입력받는 카드에 적힌 수를 모두 vector 에 push하고, 그 벡터를 정렬한 후에 vector<pair<int, int> >에 저장하면서 카드 숫자를 저장하니 시간초과를 해결할 수 있었다.

 

 

이 문제를 푼 다른 분들의 풀이를 보니, lower_bound와 upper_bound를 이용한 풀이들이 많았다.

lower_bound함수는 lower_bound(arr, arr+n, num); 와 같이 사용하고, arr ~ arr+n 까지에서 num 이상의 숫자를 찾는다면 그 위치의 iterator를 반환.

upper_bound함수도 upper_bound(arr, arr+n, num); 과 같이 사용하고, arr ~ arr+n까지에서 처음으로 num을 초과하는 숫자를 찾으면 그 위치의 iterator를 반환한다.

 

-> 위의 문제에 적용하려면, x가 적힌 카드의 개수가 몇 개인지 찾고싶을때

upper_bound(nums.begin(), nums.end(), x) - lower_bound(nums.begin(), nums.end(), x) 가 x가 적힌 카드의 개수가 된다.