BOJ 10816 숫자 카드2(C++)

숫자 카드 2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1168	546	444	49.888%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 숫자가 주어진다. 숫자 카드에 적혀있는 숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 적현 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 

3 0 0 1 2 0 0 2

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 이분 탐색

#include    <stdio.h>
#include    <vector>
#include    <algorithm>
#pragma warning(disable : 4996)
 
static std::vector<int> C;
static int F[555555];
static int N, M;
static int LOC[555555];
void bs(int loc, int i)
{
    int left = 0, right = N-1;
    int mid;
 
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (loc > C[mid])
            left = mid + 1;
        else if (loc < C[mid])
            right = mid - 1;
        else
        {
            LOC[i] = mid;
            return;
        }
    }
    LOC[i] = -1;
    return;
}
int main()
{
    int c;
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &c);
        C.push_back(c);
    }
    sort(C.begin(), C.end());
    scanf("%d", &M);
    for (int i = 1; i <= M; ++i)
        scanf("%d", &F[i]);
 
    for (int i = 1; i <= M; ++i)
        bs(F[i], i);
 
 
    for (int i = 1; i <= M; ++i)
    {
        int ans = 0;
        if (LOC[i] != -1)
        {
            int val = C[LOC[i]];
             
            for (int j = LOC[i]; j >= 0; --j)
            {
                if (val == C[j])
                    ans++;
                else
                    break;
            }
            for (int j = LOC[i]; j < N; ++j)
            {
                if (val == C[j])
                    ans++;
                else
                    break;
            }
            ans--;
        }
        printf("%d ", ans);
    }
 
    return 0;
}

숫자 카드(10815) 문제의 변형. 

다른 부분은 모두 동일하고(로직상. 코드 자체는 약간씩 다름..) 49라인부터 73라인까지를 추가했다. 

이분 탐색을 하며 해당하는 값의 위치를 저장한 것을 LOC배열에 넣어두었고

이를 이용해 해당하는 값 앞뒤로 동일한 값이 있는지 찾아주었다. 

1 3 3 3 3 3 3 4 5 

        ^ - 여기가 처음 위치라면 앞에서 같은 값이 어디까지 나오는지(이 예제에서는 2개) 뒤에서는 같은 값이 어디까지 나오는지(예제에서는 3개)

 차례대로 검색하는 방법

너무 의식의 흐름 그대로.. 코드를 짠 것 같아 알기는 어렵지 않겠지만 뭔가 훨씬 쉽고 편한 알고리즘이 있지 않을까 고민해봐야 할 것 같다.