[백준][10816번][이분탐색] 숫자 카드 2

숫자 카드 2

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

<코드>

#include <stdio.h>
#include <algorithm>
using namespace std;
int card[600000];
int serch[600000];
 
int twoserch(int left, int right, int count ,int serchnum){
    int mid = (left + right) / 2;
    int result;
    if (left > right)
        return count;
    else {
        if (card[mid] > serchnum){
            result = twoserch(left, mid-1, count, serchnum);
        }
        else if (card[mid] < serchnum)
        {
            result = twoserch(mid +1, right, count, serchnum);
        }
        else{
        
            result = twoserch(left, mid - 1, count, serchnum);
            result += twoserch(mid + 1, right, count, serchnum);
            result += 1;
        }
 
        return result;
    }
}
 
int main(void){
 
    
    int N, M;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
        scanf("%d", &card[i]);
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++)
        scanf("%d", &serch[i]);
 
    sort(card, card + N);
 
    for (int i = 0; i < M; i++){
        int searchNum = serch[i];
        int left = 0, right = N-1;
        int mid;
        int count = 0;
        
        printf("%d ", twoserch(left, right,0 , searchNum));
 
    }
    printf("\n");
 
    return 0;
}

<문제 푼 요령>

1. 이분탐색을 이용하여서 풀었다.

2. left와 right를 우리가 입력받은 배열의 index로 놓고 배열의 값과 비교하여서 이분 탐색한다.

3. 중요한건 검색하고자 하는 숫자의 개수를 카운트 해야하기 때문에 배열의[mid]값과 찾고자하는 값이 같다고 해서 여기서 탐색을 끝내면 안되고 양쪽으로 다시 탐색을 보내서 그 전체의 카운터한 값을 더해서 결과값을 표현한다.