백준 22233번 [가희와 키워드](C++) -yes6686- 티스토리

백준 문제 풀이: 22233 [가희와 키워드]

---

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

문제 설명:

초기에 n개의 키워드가 주어지고, 이후 m개의 블로그 글이 입력됩니다. 각 블로그 글에는 쉼표(,)로 구분된 키워드가 포함되며, 등장한 키워드는 삭제됩니다.

각 블로그 글이 처리된 후 남은 키워드의 개수를 출력하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<string, int> mp; // 키워드를 저장할 해시 맵

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

    int n, m;
    cin >> n >> m; // 키워드 개수 n, 블로그 글 개수 m 입력

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        mp[s] = 1; // 키워드 저장
    }

    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        string w = "";

        // 쉼표를 기준으로 키워드 파싱
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == ',') {
                if (mp.find(w) != mp.end()) {
                    mp.erase(w); // 키워드 삭제
                }
                w = "";
                continue;
            }
            w += s[j];
        }

        if (mp.find(w) != mp.end()) {
            mp.erase(w);
        }

        cout << mp.size() << '\n'; // 남은 키워드 개수 출력
    }
}

예제 입력:

5 3
map
set
queue
stack
list
map,stack
set,queue
queue

예제 출력:

3
1
1

---

코드 설명

• 핵심 알고리즘: 해시 맵을 사용하여 키워드 삭제 후 남은 개수를 빠르게 계산
• 구현 세부사항:
  • 초기에 모든 키워드를 unordered_map에 저장
  • 각 블로그 글을 쉼표(,)로 구분하여 키워드 삭제
  • 삭제 후 남은 키워드 개수를 출력
• 시간 복잡도: O(N + M), 각 키워드 삽입 및 검색/삭제가 O(1)에 가까움

---

결과

주어진 키워드 리스트에서 블로그 글이 등장할 때마다 관련 키워드를 삭제하고, 남은 키워드 개수를 빠르게 계산합니다. 해시 맵을 활용한 문제 해결을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!