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

예제 입력 1

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

예제 출력 1

3 0 0 1 2 0 0 2

---

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int CountA;
    cin >> CountA;

    unordered_map<string, int> Numbers;
    for (int i = 0; i < CountA; ++i)
    {
        string Number;
        cin >> Number;

        Numbers[Number] += 1;
    }

    int CountB;
    cin >> CountB;

    vector<int> Result(CountB);
    for (int i = 0; i < CountB; ++i)
    {
        string Number;
        cin >> Number;

        Result[i] = Numbers[Number];
    }

    for (int i = 0; i < CountB; ++i)
        cout << Result[i] << " ";
    cout << "\n";

    return 0;
}

#include <iostream>
#include <map>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int InputCount;
    cin >> InputCount;
    map<int, int> Numbers;
    for (size_t i = 0; i < InputCount; i++)
    {
        int InputNumber;
        cin >> InputNumber;
        Numbers[InputNumber]++;
    }

    cin >> InputCount;
    for (size_t i = 0; i < InputCount; i++)
    {
        int InputNumber;
        cin >> InputNumber;
        cout << Numbers[InputNumber] << "\n";
    }

    return 0;
}

 

map과 unordered_map은 둘 다 C++의 STL(Standard Template Library)에 포함된 연관 컨테이너로,

키와 값을 쌍으로 저장하고 키를 통해 값을 효율적으로 검색할 수 있습니다.

하지만 내부 구현 방식과 사용 사례에서 큰 차이가 있습니다.

아래는 이 두 컨테이너의 차이점, 장단점, 그리고 사용 사례입니다.

---

map

• 내부 구현: 레드-블랙 트리 기반 (균형 이진 탐색 트리)
• 키의 정렬 여부: 키가 항상 정렬된 상태로 저장됩니다.
• 시간 복잡도:
  • 삽입, 삭제, 탐색: O(log⁡N)O(\log N)O(logN)
• 메모리 사용량: 비교적 더 많이 사용 (트리 노드와 포인터 관리)

장점

1. 정렬된 데이터 유지:
   • 키가 정렬된 상태로 저장되므로 범위 기반 쿼리나 순차 탐색에 유리합니다.
   • 예: lower_bound, upper_bound와 같은 범위 검색 함수 사용 가능.
2. 비교 함수 커스터마이징 가능:
   • 사용자 정의 비교 연산자를 통해 정렬 기준을 지정할 수 있습니다.
3. 일관된 성능:
   • 데이터 크기와 관계없이 O(log⁡N)O(\log N)O(logN) 성능을 안정적으로 제공.

단점

1. 속도가 느림:
   • 삽입과 탐색이 O(log⁡N)O(\log N)O(logN)로, O(1)O(1)O(1) 평균 성능을 가진 unordered_map에 비해 느릴 수 있음.
2. 메모리 사용량 증가:
   • 트리 구조 관리에 필요한 추가 메모리가 필요.

---

unordered_map

• 내부 구현: 해시 테이블 기반
• 키의 정렬 여부: 키가 정렬되지 않음.
• 시간 복잡도:
  • 삽입, 삭제, 탐색: 평균 O(1)O(1)O(1), 최악 O(N)O(N)O(N) (해시 충돌 발생 시)
• 메모리 사용량: 상대적으로 더 적게 사용 (추가 포인터가 필요하지 않음)

장점

1. 빠른 접근 속도:
   • 평균 O(1)O(1)O(1) 성능을 제공하므로 대규모 데이터에 대해 빠른 삽입 및 탐색이 가능.
2. 메모리 효율적 사용:
   • 레드-블랙 트리 노드를 관리하지 않으므로 메모리 사용량이 상대적으로 적음.
3. 간단한 구조:
   • 키의 정렬이 필요 없는 경우 효율적.

단점

1. 정렬된 데이터 유지 불가:
   • 키가 정렬되지 않으므로 범위 기반 쿼리에 적합하지 않음.
2. 해시 충돌 처리 비용:
   • 키의 해시 함수가 잘 설계되지 않은 경우 충돌이 발생해 최악 O(N)O(N)O(N) 성능이 나올 수 있음.
3. 해시 함수의 제한:
   • 사용자 정의 타입을 키로 사용할 경우, 커스터마이징된 해시 함수와 비교 함수가 필요.

---

주요 차이점

특징/ map/ unordered_map

내부 구현	레드-블랙 트리	해시 테이블
정렬 여부	키가 정렬됨	키가 정렬되지 않음
삽입/탐색 시간	O(log⁡N)O(\log N)O(logN)	평균 O(1)O(1)O(1), 최악 O(N)O(N)O(N)
메모리 사용량	비교적 더 많음	상대적으로 더 적음
범위 쿼리 지원	지원 (lowerboundlower_boundlowerb​ound, upperboundupper_boundupperb​ound)	지원하지 않음
사용 사례	정렬된 데이터, 범위 쿼리	빠른 탐색이 필요한 경우

---

언제 어떤 것을 사용해야 할까?

map을 사용해야 하는 경우:

1. 키를 정렬된 상태로 유지해야 하는 경우:
   • 예: 사전순 출력, 범위 검색 (e.g., 1~100 사이의 값 찾기).
2. 범위 기반 연산이 필요한 경우:
   • lower_bound, upper_bound 등을 자주 사용하는 경우.
3. 데이터 크기가 크지 않은 경우:
   • O(log⁡N)O(\log N)O(logN) 비용이 큰 문제가 되지 않음.

unordered_map을 사용해야 하는 경우:

1. 빠른 탐색이 중요한 경우:
   • 대량의 데이터에서 특정 키를 빠르게 찾고자 할 때.
2. 정렬이 필요하지 않은 경우:
   • 데이터의 순서가 중요하지 않을 때.
3. 키의 다양성이 높은 경우:
   • 해시 충돌 가능성이 낮은 경우.

---

정리

• 정렬된 데이터가 필요하면 map을 사용.
• 빠른 데이터 접근이 중요하고 정렬이 필요 없다면 unordered_map을 사용.