[99클럽/코딩테스트 챌린지/C++] 비슷한 단어 문제 해결 과정

문제 링크

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

 

문제 상황

N개의 영어 단어 중에서 가장 긴 접두사를 공유하는 두 단어를 찾는 문제를 해결해야 했습니다. 접두사의 길이를 기준으로 두 단어의 유사성을 평가하며, 조건에 맞는 단어 쌍을 입력 순서를 유지한 상태로 출력해야 했습니다.

---

문제 원인

1. 접두사 관리
   단어의 접두사를 관리하기 위해 map<string, vector<int>>를 사용했지만, 접두사와 관련된 단어의 인덱스를 정확히 관리하지 못하면 결과가 틀리게 됩니다.
2. 입력 순서의 중요성
   접두사를 공유하는 단어 쌍이 여러 개일 경우, 가장 먼저 등장한 단어 쌍을 출력해야 했기 때문에 입력 순서를 보존하면서 결과를 처리해야 했습니다.
3. 중복 단어 처리
   동일한 단어가 여러 번 입력되는 경우를 처리하지 않으면 잘못된 결과가 나올 가능성이 있었습니다.

---

해결 방법

1. map과 set 활용
   • 접두사를 관리하기 위해 map<string, vector<int>>를 사용하여 각 접두사에 해당하는 단어의 입력 인덱스를 저장했습니다.
   • set<string>을 사용해 중복 단어를 필터링했습니다.
2. 조건에 따른 접두사 탐색
   • map을 순회하며 접두사의 길이를 기준으로 가장 긴 접두사를 찾았습니다.
   • 접두사의 길이가 같다면 입력 인덱스가 작은 쌍을 선택했습니다.
3. 입력 순서 유지
   접두사에 매칭된 단어의 입력 순서를 보존했습니다.

---

최종 코드

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

using namespace std;



int main() {
    int N;
    std::cin >> N;
    vector<string> strs = vector<string>(N);
    set<string> check;
    map<string, vector<int>> tables;

    for (size_t i = 0; i < N; i++)
    {
        cin >> strs[i];

		// 중복 단어 처리 (이미 저장된 단어는 무시)
        if (check.find(strs[i]) != check.end()) continue;
        check.insert(strs[i]);

        // 접두사 생성 및 저장
        string temp = "";
        for (char c : strs[i]) {
            temp += c;
            tables[temp].push_back(i); // 접두사별로 인덱스 저장
        }   
    }

    string MaxString = "";
    int max_prefix = 0;
    int max_prefix_order = 1e9;
    // 가장 긴 접두사 탐색
    for (const auto& pair : tables) {
        auto key = pair.first;
        auto value = pair.second;
        if (value.size() >= 2) { // 단어가 2개 이상이어야 함
            if (key.length() > max_prefix ||
                (key.length() == max_prefix && value[0] < max_prefix_order)) {
                MaxString = key;
                max_prefix = key.length();
                max_prefix_order = value[0];
            }
        }
    }


    std::cout << strs[tables[MaxString][0]] << '\n';
    std::cout << strs[tables[MaxString][1]] << '\n';
    

    return 0;
}

---

배운 점

1. 인덱스 관리의 중요성
   문제에서 입력 순서를 유지해야 하는 경우, 단순히 데이터를 저장하는 것이 아니라 입력된 순서를 보존하는 로직이 중요하다는 것을 배웠습니다.
2. map과 set의 적절한 사용
   • map을 통해 접두사와 관련된 데이터를 효율적으로 관리할 수 있었습니다.
   • set을 통해 중복 단어를 간단히 필터링할 수 있었습니다.
3. 조건 처리의 세밀함
   가장 긴 접두사를 찾는 과정에서 접두사의 길이와 입력 순서를 동시에 고려해야 했고, 이를 조건문으로 정확히 구현하는 것이 중요했습니다.
4. 코드 가독성 개선
   구조적 바인딩(auto [key, value])을 활용하여 코드를 더 간결하고 읽기 쉽게 만들 수 있었습니다.

---

결론

이 문제는 접두사 관리와 입력 순서 보존이 핵심인 문제였습니다. map과 set을 적절히 활용하여 데이터를 효율적으로 관리할 수 있었고, 조건을 꼼꼼히 처리하여 문제를 해결했습니다. 앞으로도 복잡한 조건의 문제를 다룰 때, 데이터 구조 선택과 조건 처리의 중요성을 더 신경 써야겠습니다.