[백준] 14965 Lozinke

유저가 N명이 있고 각자의 비밀번호가 주어진다

이 때 내 비밀번호가 다른사람의 substring이라면 

나의 비밀번호를 입력해서 그 사람의 계정으로 접속이 가능하다..!

문제는 모든 사람에 대해 본인의 계정을 제외한 접속가능한 다른계정의 수를 모두 찾는 것이다!

set과 map을 이용하면 풀 수 있는 문제지만 결국 못풀었다 ㅎㅎ

쉬운문젠대 왜 생각을 못했을까...! set,map마스터 해야겠다

푸는 방법은 비밀번호를 입력받으며 set에 substring을 다 넣는다

그리고 map에서 substring의 수를 +1해준다

모든 비밀번호에 대해 수행하고 마지막에 그 수를 더하고 n만큼 빼면(본인계정접속 수) 접속 가능한 다른사람계정 수가 나온다

소스코드

#include <iostream>
#include <set>
#include <map>
#include <string>
using namespace std;
set<string> s;
set<string>::iterator it;
map<string, int> mp;
string arr[20020];
int main() {
    int n; scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        string str; cin >> str;
        string sub;
        arr[i] = str;
        s.clear();
 
        int sz = str.size();
        for (int j = 0; j < sz; j++) {
            sub = "";
            for (int k = j; k < sz; k++) {
                sub.push_back(str[k]);
                s.insert(sub);
            }
        }
        for (it = s.begin(); it != s.end(); it++) mp[*it]++;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans += mp[arr[i]];
    ans -= n;
    printf("%d\n", ans);
}