C++ 해시맵 활용 : 리스트에 문자열이 있는지 검사하기 (BOJ 14425)

이 포스트에서는 자료구조 중 하나인 해시맵을 C++에서 활용하여 리스트에 문자열들을 저장하고, 해당 리스트에 어떤 문자열이 존재하는지를 검사하는 기능을 간단하게 구현해보는 내용을 다루고 있습니다.

 

예시로 풀어볼 문제는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14425번 : '문자열 집합'입니다.

 

 

14425번 : 문자열 집합

 

N개의 문자열로 이루어진 집합을 S라고 할 때, M개의 문자열을 입력받아 그들 중 집합 S에 포함되는 문자열이 몇 개나 존재하는지를 구하는 문제입니다.

집합에 포함된다는 것은 해당 문자열과 완전히 일치하는 문자열을 원소로 가지고 있다는 것을 의미합니다.

 

이 문제는 대표적인 해시맵 활용 예제로, 해시맵을 활용하여 문제를 해결해보도록 하겠습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

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

    int N, M; cin >> N >> M;

    map<string, bool> Map;

    while(N--) {
        string str; cin >> str;
        Map[str] = true;
    }

    int cnt = 0;
    while(M--) {
        string str; cin >> str;
        if(Map[str]) cnt++;
    }

    cout << cnt;
}

 

위와 같이 map을 string, bool로 설정하여 문자열을 검색하면 → 문자열의 존재 여부를 리턴해줄 수 있도록 선언해줍니다.

 

그 다음 N개의 문자열을 받아 집합 S에 해당하는 문자열들에 대해서는 true 값으로 해시맵이 연결되도록 합니다.

그리고 이후 M개의 문자열을 입력받아 Map[str]로 검색하여 true가 반환될 경우 cnt++를 해주어 카운트해줍니다.

 

 

 

위의 해설대로 풀이 코드를 작성하여 제출해보면 양호한 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.