programmers 영어 끝말잇기

programmers

level2 영어 끝말잇기

위 이미지를 클릭하면 해당 문제로 이동합니다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    unordered_map<string, int> word_table;
    int wrong ,flag = 1;

    word_table.insert({words[0], 1});

    for(int i =1; i<words.size(); i++){
        if(flag!=0 && (*(words[i-1].end()-1) != words[i][0] || word_table.find(words[i]) != word_table.end())){
            flag=0;
            wrong = i+1;//번째로 기록하기 위함
        }
        word_table.insert({words[i], 1});
    }

    if(flag==0){
        if(wrong%n==0){
            answer.push_back(n);
            answer.push_back(wrong/n);
        }
        else{
            answer.push_back(wrong%n);
            answer.push_back(wrong/n+1);
        }
    }
    else{
        answer.push_back(0);
        answer.push_back(0);
    }

    return answer;
}

해결 과정

위의 코드는 algorithm라이브러리의 find함수를 이용해 해결한 후 다른 사람의 풀이에서 힌트를 얻어 unordered map을 추가로 활용한 코드이다. 제한 사항에서 단어들의 수가 100이하이기 때문에 배열 탐색을 아무리 많이해도 시간이 많이 소요되지 않지만 unordered map을 이용하면 그 약간의 시간 마저도 단축시킬 수가 있다. 기존에는 이전에 나온 단어인지 확인하는 조건을 생각 못하고 실패한 뒤에 해당 조건을 해결하는 과정에서 unordered map을 활용하려고 했었으나 words벡터를 탐색하기 전에 insert를 하며 이상하게 활용하면서 포기했었는 데 힌트를 얻어 보다 효율적으로 해결할 수 있었다.

이전 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;

    int wrong ,flag = 1;

    for(int i =1; i<words.size(); i++){
        if(flag!=0 && (*(words[i-1].end()-1) != words[i][0] || find(words.begin(), words.begin()+i, words[i]) != words.begin()+i)){
            flag=0;
            wrong = i+1;//번째로 기록하기 위함
        }
    }

    if(flag==0){
        if(wrong%n==0){
            answer.push_back(n);
            answer.push_back(wrong/n);
        }
        else{
            answer.push_back(wrong%n);
            answer.push_back(wrong/n+1);
        }
    }
    else{
        answer.push_back(0);
        answer.push_back(0);
    }


    return answer;
}