미완성코드/(C++)2018 KAKAO BLIND RECRUITMENT[3차] 자동완성

1. 문제

programmers.co.kr/learn/courses/30/lessons/17685

코딩테스트 연습 - [3차] 자동완성

2. 풀이

약 세시간의 사투끝에.. 이 방법은 포기하는 거로 했다^^!

뭔 짓을 해도 저 7개가 시간 초과가 떠서 이 방법은 아닌거 같다..

시간 복잡도를 줄일 수 있는 새로운 알고리즘을 생각을 해봐야할듯 

 

3. 코드 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<string> words) {
    int answer = 0;
    char searchword;
    sort(words.begin(),words.end());
    int string_size = 0;
    vector<string> temp; 

    for(int i = 0; i < words.size();i++){
        temp.clear();
        for(int l = 0; l< words[i].size();l++){
            searchword = words[i][l];
            string_size = l+1;    
            if(l==0){
                bool is_same = false;
                for(int j = 0; j < words.size();j++){
                    if(searchword == words[j][0]){
                        is_same = true;
                        temp.push_back(words[j]);
                    }
                    else if(is_same){break;}
                }
            }
            else{
                sort(temp.begin(),temp.end());
                bool is_same = false;
                for(int j = 0; j < temp.size(); j++){
                    if(temp[j].length() < string_size){
                        temp.erase(temp.begin()+j);
                        j--;
                        continue;
                    }
                    if(searchword == temp[j][string_size-1]){
                        is_same = true; 
                        continue;
                    }
                    if(searchword != temp[j][string_size-1] && (!is_same)){
                        temp.erase(temp.begin()+j);
                        j--;
                        continue;
                    }
                    if(searchword != temp[j][string_size-1] && (is_same)){
                        temp.erase(temp.begin()+j,temp.end());
                        break;
                    }
                }
            }
            //다른게 없을 때
            if(temp.size() == 1){answer += l+1; break;}
            //끝까지 다 검색했을 때
            else if(l == words[i].size()-1){answer+= l+1;}
        }
    }
    return answer;
}