[개쉬운 풀이] 백준 2179 비슷한 단어

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

 

 

문제

N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

생각

1. 처음에는 단순하게 비교할 두 문자열 가져오기 => 이중포문
2. 두 문자열 접두사 비교하기 => 포문
3. 으로 생각하였다. 그러나 총 O(n^3)으로 시간초과가 발생하였다.
4. 다음은 문자열들을 받은 상황에서 sort()를 하여 사전순으로 정렬하여 붙어있는 문자열들만 비교하면 된다는 것을 깨달았다. (어차피 그 다음 문자열과는 최대 접두사가 나올 수 없기 때문에, 사전순 이므로)
5. 따라서 O(nlogn)과 이후 n개의 문자열을 문자열 길이인 m만큼 시간복잡도가 사용되므로 최종 시간 복잡도는 O(nlogn + nm)이 된다.
6. 그러나 문제는 최대 접두사를 찾은 이후다.
7. 최대 접두사의 길이가 같은 문자열들은 여러개 나올 수 있다. 따라서 나는 map<int, set<>> 를 사용하였다.
8. 출력값은 가장 먼저 넣은 문자열 우선이므로, index를 저장하여 역순으로 다시 인덱스를 찾아 출력해주었다.

풀이

1. input();
2. 문자열들을 list에 담는다 (vector)
3. 문자열들을 constList에 담는다 (vector), list는 sort하기 때문에 인덱스로 다시 문자열을 찾으려면 원본이 필요하기 때문.
4. sol();
5. list를 사전순으로 정렬한다 (sort())
6. for문을 통해 정렬된 문자열들을 i, i+1로 비교한다. 이때 N번째 오른쪽은 없으므로 N-1까지 비교한다.
7. 최대길이의 접두사가 발견되면 map을 초기화하고 새로 인덱스를 저장한다.
8. 이후 map안에 set을 활용하여 가장 작은 인덱스를 찾는다.
9. 그 인덱스가 포함된 문자열 2개를 출력한다.

 

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

int N;

vector<string> list; //정렬될 문자열 
vector<string> constList; //기존 문자열
map<string, int> getIdx;
int maxlen = 0;

void input(){
    cin >> N;
    list = vector<string> (N);
    for(int i = 0; i < N; i++){
        cin >> list[i];
        constList.push_back(list[i]);
        getIdx.insert({list[i], i}); //기존 문자열의 들어온 번호 저장
    }
}

//두 문자열의 접두사 길이 찾기
int process(string A, string B){
    int len = min(A.length(),B.length());
    int count = 0;
    for(int i = 0; i < len; i++){
        if(A[i] == B[i]) count++;
        else break;
    }
    return count;
}


void sol(){
    sort(list.begin(), list.end());
    map<int,set<int>> answer;
    int maxlen = 0;
    int key = 0;
    //정렬해서 옆에 문자와 비교하면 된다.
    for(int i = 0; i < N-1; i++){
    	//두 문자열의 최대 접두사 길이
        int count = process(list[i], list[i+1]);
        
        //같은 접두사를 저장하기 위함
        if(maxlen < count){ //기존 최대 길이 보다 더 큰 경우
            key++;
            maxlen = count;
            answer = map<int,set<int>>(); //초기화를 통해 최대 길이만 넣는다
            answer[key].insert(getIdx[list[i]]);
            answer[key].insert(getIdx[list[i+1]]);
        }
        else if(maxlen == count){ //최대 길이의 접두사를 사용하는 경우
            answer[key].insert(getIdx[list[i]]);
            answer[key].insert(getIdx[list[i+1]]);
        }
        else{
        	//길이가 달라지면 접두사가 바뀐다.
            //따라서 key를 변경시켜 같은 접두사를 사용하면 그대로 Insert 아니면 다음키에 저장
            key++;
        }
    }
    int ansKey = 0;
    int ansIdx = 1e9;
    
    //같은 길이의 접두사 중에서 가장 먼저 들어온 문자를 찾기 위함
    for(auto tmp : answer){ //answer = map<int, set<int>>
        for(auto idx : tmp.second){ //tmp.second = set<int>
            if(idx < ansIdx){ //set을 사용했으므로 그 안에서 가장 작은 idx가 나온다.
                ansIdx = idx;
                ansKey = tmp.first; //출력해야하는 idx 모음들을 찾으면 key 저장  
            }
            break;
        }
    }
    int flag = 2;
    //key를 통해 set<int>를 찾고 맨 앞 2개만 출력한다.
    for(auto idx : answer[ansKey]){
        if(flag == 0) break;
        
        cout << constList[idx] << endl;
        flag--;
    }
}

int main(){
    input();
    sol();
    return 0;
}

되게 어려운 문제다.