백준 22233번 가희와 키워드 (C++)

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

22233번: 가희와 키워드

 

문제 요약

 

1. n개의 문자 키워드와 m개의 테스트 케이스가 주어집니다. (1<=n,m<=2*10^5)

2. 키워드는 소문자와 숫자로만 이루어져있습니다.

3. m개의 테스트 케이스에는 각각 문자열 하나가 주어지며, 문자열 내부에는 여러개의 키워드가 ','로 구분되어 주어집니다.

(1 <= 문자열에 있는 키워드의 갯수 <= 10)

4. 3번의 문자열에는 중복된 키워드가 존재하지 않지만, 한 키워드가 여러개의 테스트 케이스에 사용될 수 있습니다.

5. 각 테스트 케이스를 실행할때마다 해당 테스트케이스에 사용된 키워드가 n개의 문자열 키워드에 존재할 경우, 해당 키워드는 삭제됩니다.

6. 각 테스트 케이스를 실행할때마다 남는 문자 키워드의 갯수를 출력하세요.

 

핵심 포인트

 

Python이나 Java로 풀었다면 쉬웠을 문제였지만, C++은 문자열관련 알고리즘에 불친절한 경향이 있습니다.

때문에 시간초과나 문자열관련 함수 사용에 주의를 기울여야합니다.

 

1. 시간초과

무턱대고 unordered_map으로 접근했다가 시간초과가 발생합니다.

문제를 잘 보면 n개의 키워드 내에 중복되는 키워드는 없으므로, unordered_map을 사용할 필요가 없습니다.

대신에 unordered_set을 사용하고 각 테스트 케이스마다 사용된 문자열을 지워주면 unordered_map보다 빠르게 접근할 수 있습니다.

 

2. 문자열관련 함수

C++의 find, substr, string::npos를 잘 이해해야합니다.

눈여겨볼 특징으로 substr(a,b)는 a번째부터 시작하여 b-1개의 문자열을 가져옵니다.

예를들어 substr(5,3)이라면 5,6,7번째 문자를 가져옵니다.

find함수에서 결과값이 여러가지일 경우, 가장 최초로 발견한 위치만을 반환합니다.

npos의 경우 일반적으로 쓰레기값이 들어가며, find를 통해 해당 문자를 찾지 못할 경우 npos를 반환합니다.

    string s = "abcde";
    int pos = 0;
    if(s.find('a')!=s.npos) cout << s.find('a') << "\n"; // 문자열 s에 'a'가 존재하는가
    if(s.find('a',0)!=s.npos) cout << s.find('a',0) << "\n"; // 문자열 s의 0번째부터 시작해서 'a'가 존재하는가
    if(s.find('a',4)==s.npos) cout << "없습니다" << "\n"; // 문자열 s의 4번째부터 시작해서 'a'가 존재하는가
    cout << s.substr(0,3) << "\n"; // 문자열 s의 0번째이상, 3번째 미만의 문자를 출력하라
    cout << s.substr(0) << "\n"; // 문자열 s의 0번째이상을 모두 출력하라

[결과]
0
0
없습니다
abc
abcde

결론적으로 모든 조건문이 true입니다.

 

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 입력받습니다.

    int n,m,total = 0;
    string s="",temp="",k="";
    unordered_set<string> st;
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> s;
        st.insert(s);
    }

unordered_set을 사용하기위해 헤더함수에 <unordered_set>을 추가해야합니다.

 

2. m번만큼 테스트 케이스를 입력받습니다.

while(m--){
        cin >> temp;
        int pos = 0;
        while(pos<temp.length()){ // 1
            auto it = temp.find(',',pos); // 2
            if(it==temp.npos){ // 3
                k = temp.substr(pos); // 4
                if(st.find(k)!=st.end()) st.erase(k); // 5
                break;
            }
            else{ 
                k = temp.substr(pos, it-pos); // 6
                if(st.find(k)!=st.end()) st.erase(k); // 7
                pos = it+1; // 8
            }
        }
        cout << st.size() << "\n"; // 9
    }

(1) pos가 temp의 length()미만일때까지 while문을 진행합니다.

(2) it변수는 int형입니다. 편의상 auto로 선언했습니다. 

pos번째 이상부터 조사하여 ','의 위치를 찾아 it에 저장합니다.

> (3) 만약 ','가 존재하지 않을 경우

> (4) pos이상부터 temp의 끝까지를 k에 저장합니다.

> (5) st에서 k를 발견할 경우 k를 지웁니다. 그리고 while문을 빠져나옵니다.

반대로 pos번째 이상부터 조사하여 ','의 위치가 발견될 경우

> (6) pos부터 시작해서 ','가 발견된 위치 바로 직전까지의 문자열을 가져옵니다.

> (7) st에서 k를 발견할 경우 k를 지웁니다.

> (8) pos는 ','가 발견된 위치 +1에서 부터 시작되어야하므로, pos = it+1로 저장합니다.

(9) 최종적으로 남은 st의 사이즈를 출력합니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <cstring>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,total = 0;
    string s="",temp="",k="";
    unordered_set<string> st;
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> s;
        st.insert(s);
    }
    while(m--){
        cin >> temp;
        int pos = 0;
        while(pos<temp.length()){
            auto it = temp.find(',',pos);
            if(it==temp.npos){
                k = temp.substr(pos);
                if(st.find(k)!=st.end()) st.erase(k);
                break;
            }
            else{
                k = temp.substr(pos, it-pos);
                if(st.find(k)!=st.end()) st.erase(k);
                pos = it+1;
            }
        }
        cout << st.size() << "\n";
    }
    return 0;
}

위 코드는 640ms가 소비되었습니다.