시작

우선 이문제는 생각보다 너무 복잡한 문제다. 전 단어의 끝문자와 현재 단어의 첫 문자가 같은지 확인을 해야하며, 몇번째에서 틀렸는지, 몇번째 사람 차례인지도 확인을 해야하기에 어려운 문제다. 그렇다면 어떻게 풀었는지 한번 보자.

1. 우선 범위가 벗어났는지 확인
2. 첫번째면, 그냥 단어 넣고 아니면 단어를 넣으면서 단어가 중복되는지, 끝말잇기에 위배되는지 확인

간단한 알고리즘으로 표현이 되는데, 이제 이것을 어떻게 풀었는지 말하자면, 우선 중복 단어는 cpp에서 map이라는 것으로 확인을 할 수 있다. 우선 map의 형식은 우리가 흔히아는 dictionary형식으로
<type, type> 형태로 집어 넣을 수 있다는 점이 있다. 이것을 이용해 <string, int>형을 제작해, word["단어"]의 있는 정수형이 1이면 이미 사용한 단어고 0이면 사용을 안한 단어라고 생각하고 제작을 하였다. 그리고 몇번째 차례인지 확인하는 변수와, 지금 현재 몇번 째 단어를 사용하고 있는 변수도 제작해, 확인할 수 있게 제작하였다. 그럼 한번 코드를 보자.

코드

#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    // 어느 차례의 누가 말했는지 확인하는 배열
    vector<vector<string>> answers(n+1);
    // 몇번째 단어
    int s = -1;
    // 차례 확인
    int i = 0;
    // 체크용
    bool check1 = false, check2 = false;
    // 단어를 사용했는지 확인
    map<string, int> word;
    // 일단 계속 확인
   while(true){
       i++;
       s++;
       // 만약 범위가 벗어나면 멈추기
       if (words.size()-1 < s) break;
       // 첫번째 단어는 넘기기
       if (s == 0) {
           answers[i].push_back(words[s]);
       }
       else {
           answers[i].push_back(words[s]);
           // 만약 사용한 단어거나, 끝말잇기에 위배되는지 확인
           if ((word[words[s]] == 1 || words[s - 1][words[s - 1].size()-1] != words[s][0])) {
               check1 = true;
               break;
           }
       }
       // 단어 사용 체크
        word[words[s]]++;
        // n번째 까지 확인했으니 초기화
        if (i == n) {
            i = 0;
        }
    }
   // 만약 룰을 어겼으면 i번째 사람
   if (check1) {
       answer.push_back(i);
   }
   // 룰을 어기지 않았으므로 0
   else {
       answer.push_back(0);
   }
   // 만약 범위를 벗어나면 -1
   if (s >= words.size()) {
       s--;
   }
   // i번째 사람이 룰을 어겼으니 확인
   for (int j = 0; j < answers[i].size(); j++) {
       // 만약 룰을 어긴 사람의 단어중, 위배되는 단어가 있는지 체크
       if (answers[i][j] == words[s]) {
           // 있으니 j번째 단어임을 암시
           answer.push_back(j+1);
           check2 = true;
           break;
       }
   }
   // 없으면 0
   if (!check2) {
       answer.push_back(0);
   }
    return answer;
}