[BOJ 10816번/C++] 숫자 카드 2

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

10816번: 숫자 카드 2

숫자 카드 2

문제

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

풀이

먼저 배열의 크기가 매우 크다. 그리고, 탐색 문제임이 보이기에 이 문제는 이진 탐색을 이용해서 풀어야한다.

 

그런데, 리스트에 중복된 값이 있고 그 중복된 수를 구해야한다.

이럴 때에는 이진 탐색을 조금 변환한 알고리즘인 lower_bound와 upper_bound를 사용한다.

 

lower_bound는 찾는 값 k가 처음 나오는 위치를 찾아준다.

upper_bound는 찾는 값 k가 마지막으로 나오는 위치 + 1을 찾아준다.

 

즉, upper_bound 결과 - lower_bound 결과 한 값이 k의 수가 된다.

 

#include <cstdio>
#include <algorithm>

int card[500000];
int N, M;

int main() {
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &card[i]);
    }

    std::sort(card, card + N);

    scanf("%d", &M);

    int find;
    for (int i = 0; i < M; i++) {
        scanf("%d", &find);
        printf("%d ", std::upper_bound(card, card + N, find) - std::lower_bound(card, card + N, find));
    }

    return 0;
}