📒활용개념

1.map을 활용한 문제풀이
2.n의 길이가 작기 때문에 이중 for문(O(n*n))을 사용해도 시간복잡도를 넘기지 않는다.

📌문제설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

-조건
- 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
- 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
- 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
- 이전에 등장했던 단어는 사용할 수 없습니다.
- 한 글자인 단어는 인정되지 않습니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

• 제한 사항

  	- 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
  	- words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
  	- 단어의 길이는 2 이상 50 이하입니다.
  	- 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
  	- 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
  	- 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
  	- 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

📌구현

1. 이중 for문을 활용한 문제풀이
   • 제한 사항에서 words의 길이가 100이하이기 때문에 할 수 있는 문제풀이

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

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer(2);					//answer{0,0}으로 초기화
    vector<int> count(n+1);					//n번 째 사람이 말한 횟수
    bool check = false;						//단어를 사용 했는지 검사
    
    count[1]++;
    for(int i=1; i<words.size(); i++){
        count[(i%n)+1]++;
        int size=words[i-1].size()-1;		//앞의 단어의 마지막 글자
        
        //조건 3확인
        if(words[i][0]!=words[i-1][size]){
            answer[0] = (i%n)+1;
            answer[1] = count[(i%n)+1];
            break;
        }
        
        //조건 4확인
        for(int j=0; j<i; j++){
            if(words[i]==words[j]){
                check=true;
                answer[0] = ((i%n)+1);
                answer[1] = (count[(i%n)+1]);
            }
        }
        if(check){
            break;
        }
    }
    
    return answer;
}

2. map을 이용한 문제풀이
   • words의 길이에 상관없이 사용할 수 있는 문제풀이

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

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer(2,0);
    map<string, int> word;
    
    word[words[0]]++;
    
    for(int i=1; i<words.size(); i++){
        if(word[words[i]] ||words[i].front()!=words[i-1].back()){
            answer[0]=(i%n)+1;
            answer[1]=(i/n)+1;
            break;
        }
        word[words[i]]++;
    }

    return answer;
}

📌주의점

• n의 크기가 작다면 for문을 사용해도 부담이 없기 때문에 처음에는 for문으로 문제를 해결했다.
• 하지만 n의 크기가 커진다면 시간복잡도에서 걸리기 때문에 map을 통한 문제풀이를 다시 했다.