[코드포스 Practice20] D. BerOS File Suggestion

아 저번주 토요일날 밤을 새서라도 끝냈어야 했는데

5일 지나니깐 기억이 안 나서 힘들었음

풀이 듣고 재밌었던 문제

전처리 하는 문제는 항상 신기하고 기발한 것 같음

어떻게 이렇게 풀 수 있지???

휴 map 쓴다고 힘들었다.

map이랑 pair형 벡터랑 자꾸 헷갈려 가지고 m[s] 이런식으로 접근 하는걸 자꾸 까먹는다.

 

 

sudstr도 처음 써보는데 잘 돌아가는지 궁금해서 확인해봤음

 

다행히 잘 돌아간다.

 

이 문제 처음 풀 때 틀렸었다.

 

디버깅 해보니 aaa이런 문자열이 들어오면 a 한 번만 인덱스를 넣어줘야 하는데 중복 제거를 안 했었다ㅋㅋ

 

sort(m[s].begin(), m[s].end()); 
m[s].erase(unique(m[s].begin(), m[s].end()), m[s].end());

 

정렬 - unique - erase로 중복된 값들을 제거해줬다.

 

그러면서 중복 허용하지 않으니깐 vector 대신 set으로 하는 건 어떨까 싶었음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);
    
    map <string, set<int>> m;
    vector <string> v;
    for (int k = 0; k < n; k++)
    {
        string s;
        cin >> s;
        
        v.push_back(s);
        for (int i = 1; i <= s.size(); i++)
        {
            for (int j = 0; j <= s.size()-i; j++)
            {
                m[s.substr(j, i)].insert(k);
            }
        }
    }
    
    int q;
    scanf("%d", &q);
    
    for (int k = 0; k < q; k++)
    {
        string s;
        cin >> s;
        
        cout << m[s].size() << " ";
        
        if (m[s].size() == 0)
        {
            cout << "-\n";
            continue;
        }

        cout << v[*m[s].begin()] << " ";
        cout << endl;
    }
    
    return 0;
}

 

이건 set 사용한 코드

 

set은 insert로 값을 넣었었지... 너무 헷갈리고 안 외워짐