[백준 22233] - 가희와 키워드(해시, 파싱) C++

문제

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

접근방법

포인트는 2가지이다. parsing과 unordered_set 사용.

 

인풋값이 아래와 같이 크기때문에 최대한 시간을 줄이는 방법을 택해야한다.

• 1 ≤ N ≤ 2×10^5 
• 1 ≤ M ≤ 2×10^5

map에서 접근 시간은 O(1)로 알고있었는데, map을 사용하니 시간초과가 났다.

알고보니 O(1)이 아니었다.

map과 set은 둘 다 red-black-tree를 사용하고,

unordered_set은 hash-table을 사용한다고 한다.

다음을 참고하자.

 

- **std::map**
    - **Find:** O(log n) (finding a value by key)
    - **Inserting:** O(log n)
    - **Deleting:** O(log n)
- **std::set**
    - **Find:** O(log n) (finding an element)
    - **Inserting:** O(log n)
    - **Deleting:** O(log n)
- **std::unordered_set**
    - **Find:** Average O(1), Worst O(n) (finding an element)
    - **Inserting:** Average O(1), Worst O(n)
    - **Deleting:** Average O(1), Worst O(n)

 

문자열을 파싱하기 위해서, sstream을 사용했다.

stringstream ss(문자열)으로 문자열 스트림을 만든후에

getline(ss, token, ',') 함수를 호출해 쉼표를 기준으로 token을 하나씩 받아왔다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_set>


using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define _FOR(i, s, n) for (int i=s;i<(n);++i)
#define FASTER ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 987654321


int n, m;

int main() {
    FASTER

    int n, m;
    cin >> n >> m;

    unordered_set<string> keywords;
    string temp;

    // Reading keywords
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        keywords.insert(temp);
    }

    // Processing each string separated by commas
    for (int i = 0; i < m; ++i) {
        cin >> temp;
        stringstream ss(temp);
        string token;
        while (getline(ss, token, ',')) {
            if (keywords.find(token) != keywords.end()) {
                keywords.erase(token);
            }
        }
        cout << keywords.size() << "\n";
    }

    return 0;
}

개선할 점

문자열 파싱과 해싱에 많이 약함을 깨달았다.

 

그리고 특히 IO operation 수행 횟수가 많은 경우에는 꼭 FASTER 매크로과 '\n'을 사용해야한다.

 

unordered_set의 시간 효율성이 아주 좋다는 걸 깨달았다. 이제 많이 써봐야겠다.