반응형
이분탐색 문제였습니다.
하지만 원하는 카드 값을 찾는 부분에서 시간 초과가 나기 쉬운데요 그때는 하나하나 값을 찾아 더하기 보다는 upper_bound와 lower_bound의 차이를 이용하면 간단히 구할 수 있습니다.
<algorithm> 라이브러리를 통해 lower_bound, upper_bound를 사용할 수 있습니다.
제가 만든 함수는 위 라이브러리가 지원하는 함수와 같은 기능을 합니다. 코드 하단 주석을 보시면 라이브러리 함수 를 사용하는 방법을 써 놓았습니다.
lower_bound(배열의 시작 인덱스,배열의 끝 인덱스,찾고자 하는 값) : 찾고자 하는 값이 가장 처음 나오는 인덱스(위치)를 반환하는 함수입니다.
upper_bound(lower_bound와 같습니다.) : 찾고자 하는 값보다 큰 값이 가장 처음 나오는 인덱스(위치)를 반환하는 함수입니다. 만약 없을 경우 자동으로 배열의 마지막 인덱스+1 값을 반환합니다.
위 두 함수나 이분탐색을 사용하기 위해서는 무조건 먼저 sorting이 되야 합니다.
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 | #include <iostream> #include <algorithm> //upper_bound, lower_bound 함수 라이브러리 using namespace std; int n, m, card, l, r; int c[500001]; int l_bound(int l, int r)//찾는 값이 처음 나오는 위치 { while (l < r) { int mid = (l + r) / 2; if (c[mid] < card) l = mid + 1; else r = mid; } return l; } int u_bound(int l, int r)//찾는 값보다 큰 친구가 처음 나타나는 위치 { while (l < r) { int mid = (l + r) / 2; if (c[mid] <= card) l=mid+1; else r = mid; } return r; } int main() { cin.tie(NULL); ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) cin >> c[i]; sort(c+1,c+n+1);//오름차순으로 정렬 cin >> m; for(int i = 1; i<=m; i++) { l = 1; r = n+1; cin >> card; /* auto l = lower_bound(c+1, c+n+1, card); lower_bound : 찾고자 하는 값 또는 큰 값이 처음 나오는 인덱스(위치) auto r = upper_bound(c+1, c+n+1, card); upper_bound : 찾고자 하는 값보다 큰 값이 처음 나오는 인덱스(위치) 찾고자 하는 값보다 큰 값이 없으면 자동으로 그 다음 인덱스 반환 */ l = l_bound(l, r); r = u_bound(l, r); cout << r - l << ' '; } } | cs |
'Algorithm' 카테고리의 다른 글
| (C++) - 백준(BOJ) 2484번 : 주사위 네개 답 (0) | 2019.02.10 |
|---|---|
| (C++) - 백준(BOJ) 7572번 : 간지(干支) 답 (0) | 2019.02.08 |
| C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1676번 : 팩토리얼 0의 개수답 (0) | 2019.01.28 |
| C++(씨쁠쁠)(cplusplus) - 백준(baekjoon)(BaekJoon)코딩 15552번 : 빠른 A+B 답 (0) | 2019.01.28 |
| C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 10984번:내 학점을 구해줘 답 (0) | 2019.01.25 |