05_03 [기출문제] 정렬된 배열에서 특정 수의 개수 구하기

01 당장 좋은 것만 선택하는 그리디

02 아이디어를 코드로 바꾸는 구현

03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS

04 기준에 따라 데이터를 정렬

05 범위를 반씩 좁혀가는 탐색

06 다이나믹 프로그래밍

07 가장 빠른 길 찾기

08 다양한 그래프 알고리즘

 

[문제]

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2 ,2 ,2 ,2, 3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 ‘시간 초과’ 판정을 받습니다.

[입력 조건]

• 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1 <= N <= 1,000,000, -1e9 <= x <= 1e9)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-1e9 <= 각 원소의 값 <= 1e9)

[출력 조건]

• 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단 값이 x인 원소가 하나도 없다면 -1일 출력합니다.

입력예시1

7 2
1 1 2 2 2 2 3

출력예시1

4

입력예시2

7 4
1 1 2 2 2 2 3

출력예시2

-1