[C++] 백준 2179번 : 비슷한 단어

🔗 문제

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

 

 

✏️ 풀이

1. 입력을 N번 받는다. 입력받은 문자열이 중복이면 저장하지 않고 무시한다.
   1. std::set<std::string> check 변수로 중복 확인을 하며, 오직 중복 확인만을 위해 사용한다.
2. 입력받은 문자T를 앞에서 하나씩 떼어서 부분 문자열을 만든 후, 현재 입력받은 순서를 저장한다.

abc -> {a, ab, abc}
ab -> {a, ab}

map에는 {a, {0, 1}}, {ab, {0, 1}}, {abc, {0}} 이렇게 저장된다.

1. 부분 문자열을 만들고 map에 저장하는 과정에서 가장 긴 prefix의 길이를 갱신한다. (max_prefix)

 

map의 key-value 

• key : prefix
• value : 해당 prefix를 만들 수 있는 문자열T의 입력 순서 (이미 정렬되어 있다.)

 

입력이 끝난 후 모든 맵을 순회하면서 정답을 찾는다.

 

조건

1. key 길이가 max_prefix와 같다. (가장 긴 접두사 찾기)
2. value의 크기가 2 이상이다. (비슷한 단어의 조건)
3. 위 두 조건이 만족하는 동시에 value[0]의 가장 작은 값을 찾는다.

 

<반례 - 96% 틀렸습니다> - 스터디원 유미가 찾아줌 🎶

4
ab
bca
bcb
abd
//answer 
// ab
// abd
// 이 반례덕분에 입력하면서 정답 찾기 X -> 마지막에 순회하는 걸로 바꿔서 통과함

 

💾  소스

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    
    std::string T;
    std::vector<std::string> input;
    std::set<std::string> check;
    std::map<std::string, std::vector<int>> map;

    int max_length = 0;
    int max_prefix_order = 1e9;
    std::string max_prefix;
    
    int N;
    std::cin >> N;
    input.resize(N);
    for(int i=0; i<N; ++i)
    {
        std::cin >>  T;
        input[i] = T;

        if(check.find(T) != check.end()) continue;
        check.insert(T);

        std::string tmp="";
        for(int s=0; s<T.size(); ++s)
        {
            tmp += T[s];
            map[tmp].push_back(i);

            if(map[tmp].size() > 1 && max_length < tmp.length())
            {
                max_length = tmp.length();
            }
        }
    }

    for(const auto& [key, value] : map)
    {
        if(value.size() >=2 && key.length() == max_length)
        {
            if(value[0] < max_prefix_order)
            {
                max_prefix_order = value[0];
                max_prefix = key;
            }
        }
    }

    std::cout << input[map[max_prefix][0]] << "\\n" << input[map[max_prefix][1]];
    return 0;
}