[백준 알고리즘] 10816번: 숫자카드2

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

문제

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

풀이

시도해본 방법 1 : 이진탐색 연속호출

가장 처음 시도해본 방법은 이진탐색으로 일단 하나를 찾고, 이진탐색의 시작 인덱스를 방금 찾은 위치 바로 다음으로 잡아서 탐색 결과가 실패(-1) 이 나올 때까지 반복하는 방법이었다. 쉽게 풀릴 줄 알았는데, 테스트케이스를 통과하지 못했다. 디버깅하면서 이유를 찾아 보니 이런 방법으로는 문제가 안풀리는 것이 매우 당연했다. 이진탐색은 중간 인덱스를 기준으로 값을 찾기 때문에 같은 값이 여러개 있으면 항상 첫번째 값을 먼저 찾는다는 보장이 없다.

시도해본 방법 2 : 맵 이용하기

그래서 생각한 방법이 map 컨테이너를 이용해서 푸는 방법이다. 각 숫자를 key로 만들고 카드의 개수를 value로 잡은 뒤, 찾고자하는 숫자를 find 함수로 찾아 value 값을 참조하기만 하면 해결됐다. STL 을 활용해서 쉽게 해결할 수 있는 문제였다.

코드

#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    int N, M, target;
    map<int, int> cards;

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

    scanf("%d", &M);
    while (M--)
    {
        scanf("%d", &target);
        auto iter = cards.find(target);
        if (iter == cards.end())
            printf("0 ");
        else
            (printf("%d ", (*iter).second));
    }
}