[C++/Programmers] Lv2. 영어 끝말잇기

Lv2 문제이다.

 

---

끝말잇기 탈락자를 가려내며, 몇 번째 탈락자인지 가려내는 것이 목적이다.

 

끝말잇기의 기본 조건은 앞에 있는 문자열의 맨 뒤 문자와 뒤에 있는 문자열의 맨 앞 문자가 같아야 하며, 뒤에 말한 단어가 앞서 말했던 단어들이랑 같지 않아야 한다. (단어가 겹치지 않아야 함)

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    vector<int> cnt;
    int order = 0; // 끝말잇기 순서
    
    for(int i=0;i<n;i++){
        cnt.push_back(0); // 몇 번째 순서인지 카운트하는 벡터
    }
    
    
    for(int i = 0;i<words.size();i++){
        if(i == 0){
            cnt[order]++;
            if(order == n-1)
                order = 0;
            else
                order++;
            continue;
        }
        
        cnt[order]++;
        if(words[i-1][words[i-1].length()-1] == words[i][0]){
            
            for(int j=0;j<i;j++){
                if(words[j].compare(words[i]) == 0){
                    answer.push_back(order+1);
                    answer.push_back(cnt[order]);
                    return answer;
                }
            }
            
            if(order == n-1)
                order = 0;
            else
                order++;
            
        }else{
            answer.push_back(order+1);
            answer.push_back(cnt[order]);
            break;
        }
        
        
    }
    
    if(answer.size() == 0){
        answer.push_back(0);
        answer.push_back(0);
    }

    return answer;
}

 

사람들이 각각 몇 번째 차례인지 넣을 vector를 하나 마련해 주었으며 조건을 넣어 벡터가 계속 반복되게 만들어 주었다.

 

그리고, compare와 for 문을 이용하여 앞서 말했던 단어까지 같은 단어가 있었는지 비교 하여 만약 탈락하게 되면 answer에 넣어 주어 return 해 준다.