몸풀기 1

[배열] 숫자값을 인풋으로 받아서 정렬된 정수배열에서 얼마나 등장하는지 찾기 (제한 시간복잡도 O(log N))

예를들어 3과 [1,1,3,3,4,4,4] 이 나오면 3이 두번 나오므로 2.

입력

3

1 1 2 2 3 3 4 5 

출력

2

====================

#include<cstdio>

int main()

{

int fn, temp, cnt = 0;

for (scanf("%d", &fn); scanf("%d", &temp) != EOF;)

cnt = (fn == temp) ? (cnt + 1) : cnt;

printf("%d", cnt);

}

//입력을 받으면서 바로 카운트를 세어보았습니다.

=======================

#include<cstdio>

#include<vector>

using namespace std;

int main()

{

vector<int> v;

int fn, temp, cnt = 0, front = 0, middle, end;

scanf("%d", &fn);

while (scanf("%d", &temp) != EOF)

v.push_back(temp);

for (end = v.size(); front <= end;)

{

middle = (front + end) / 2;

if (fn == v.at(middle))

break;

else if (fn > v.at(middle))

front = middle + 1;

else

end = middle - 1;

}

if (middle < v.size() - 1)

for (temp = middle; fn == v.at(temp++);)

{

++cnt;

if (temp == v.size() - 1)

break;

}

if (middle > 0)

while (fn == v.at(--middle))

{

++cnt;

if (middle == 0)

break;

}

printf("%d", cnt);

}

//배열을 받고 이진 탐색으로 위치를 찾은 다음, 양쪽으로 이동하며 해당하는 갯수를 더해보았습니다.

=====================