2179 - 비슷한 단어

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

2179번: 비슷한 단어

과정

1. 입력을 받은 뒤 입력 받은 걸 길이를 하나씩 늘려가며 일치하는게 있는지 확인한다.
2. 단순히 찾는건 오래걸리므로 map의 lower_bound를 이용한다.
3. 찾아낸 string의 접두어가 일치하는지 확인한다.
4. 문자열의 접두어 길이가 더 긴지 확인한다.
5. 찾아낸 문자열의 접두어 길이가 같다면 해당 문자열의 idx가 저장된 idx보다 앞서는지 확인한다.
6. map에 없는 문자열이라면 저장하고 끝!

예제

3
ab
abc
abd


ab
abc

4
aa
bb
bc
aj


aa
aj

코드

#include<iostream>
#include<map>
#include<string>

using namespace std;

int N;
map<string, int> m;

void solution(){
    string input;
    pair<int, int> cnt = {0, 987'654'321};
    pair<string, string> ans;

    cin>>N;
    for(int idx = 0; idx < N; ++idx){
        cin>>input;

        if(m.find(input) != m.end())
            continue;

        for(int i=cnt.first;i<=input.length();++i){
            string str = input.substr(0,i);

            auto it = m.lower_bound(str);

            if(it != m.end()){
                string findStr = it->first;

                if(findStr.substr(0,i).compare(str) == 0 ){
                    if((i == cnt.first && m[findStr] < cnt.second) || i > cnt.first){
                        ans = {findStr, input};
                        cnt = {i, m[findStr]};
                    }
                }
            }
        }

        m[input] = idx;
    }

    cout<<ans.first<<'\n'<<ans.second<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();    

    return 0;
}