Total Articles 494
[문제]
정렬이 되어 있으면서 / 중복이 가능한 / 갯수(n)가 많은 배열이 있다. 임의의 수 k가 주어 졌을 때 배열 안에 k가 몇개가 있는지 알아 내는 함수를 만들어라.
#include <iostream> using namespace std; typedef int val; // value typedef int idx; // index static const idx INVALID_INDEX = -1; idx getLeftIndex(val* arr, idx l, idx r, int k) { while (l <= r) { idx p = (l + r) / 2; // pivot if (arr[p] == k) { if (p == l) return p; if (arr[p - 1] < k) return p; r = p - 1; } else if (arr[p] < k) l = p + 1; else r = p - 1; // arr[p] > k } return INVALID_INDEX; } idx getRightIndex(val* arr, idx l, idx r, int k) { while (l <= r) { idx p = (l + r) / 2; // pivot if (arr[p] == k) { if (p == r) return p; if (arr[p + 1] > k) return p; l = p + 1; } else if (arr[p] < k) l = p + 1; else r = p - 1; // arr[p] > k } return INVALID_INDEX; } int getCount(val* arr, int n, val k) { int lIndex = getLeftIndex(arr, 0, n - 1, k); if (lIndex == INVALID_INDEX) return 0; int rIndex = getRightIndex(arr, 0, n - 1, k); if (lIndex == INVALID_INDEX) return 0; return rIndex - lIndex + 1; } void test1() { val arr[] = { 1, 2, 3, 4, 5, 5, 5, 7, 8, 9 }; int c = getCount(arr, sizeof(arr) / sizeof(val), 5); cout << c << endl; } void test2() { val arr[] = { 5, 5, 5, 5, 5, 5, 5, 7, 8, 9}; int c = getCount(arr, sizeof(arr) / sizeof(val), 5); cout << c << endl; } void test3() { val arr[] = { 1, 2, 3, 5, 5, 5, 5, 5, 5, 5}; int c = getCount(arr, sizeof(arr) / sizeof(val), 5); cout << c << endl; } int main() { test1(); test2(); test3(); }
[소스 코드]