[백준] 10816번 숫자 카드 2

 

 

문제

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include<unordered_map>
#include<stdio.h>
int main() {
    int N{}, M{};
    int value{};
    std::unordered_map<int,int>numberCards;
    
    /*
    N: 숫자카드 개수
    */
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &value);
 
        numberCards[value]++;
    }
 
    /*
    M: 가지고 있는 카드개수
    */
    scanf("%d", &M);
    for (int i = 0; i < M; ++i) {
        scanf("%d", &value);
        printf("%d ", numberCards[value]);
    }
 
}

후기

이 문제를 해결하기 위한 키워드는 이분 탐색(Binary Search)이다.

 

이분 탐색을 구현하거나 C++ 표준 함수인 std::binary_Search()을 사용해서 풀어도 되지만 나는 unordered_map을 사용해서 풀었다. unordered_map은 정렬을 보장하지 않는 대신에 해쉬 함수를 이용해서 저장을 하는 속도가 빠른 자료구조이다. 순서가 필요해 보일 수 있는데 입력을 나중에 받기 때문에 입력받은 순서대로 출력하게 하면 문제없이 통과할 수 있다. 시간에 민감한 문제이기 때문에 std::cout(), std::cin() 같은 속도가 느린 함수가 아닌 C표준함수 printf(), scanf()을 사용해서 풀었다.

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/10816

 

관련 글

[프로그래밍/Modern C++] - [C++] 연관 컨테이너 맵(map)

[온라인 코딩/탐색(Search)] - [백준] 1620번 나는야 포켓몬 마스터 이다솜