[ 프로그래머스 영어 끝말잇기 (Lv2) ] (C++)

프로그래머스의 영어 끝말잇기(Lv2) 문제이다.

 

[ 문제풀이 ]

영어 끝말잇기를 진행할 때, 탈락자가 누구인지 그리고 몇 번째에 탈락을 하는지 구해야 하는 문제이다.

영어 끝말잇기를 할 때의 조건들을 통해서 어떤 자료구조들로 주어진 정보를 관리하는 방법부터 정답을 도출하는 과정까지

진행해보자.

 

#1. 끝말잇기 규칙

문제에서 제시한 끝말잇기의 규칙이 있다. 너무나도 익숙한 규칙들이지만 중요한 것들만 한번 더 정리를 해보고 시작해보자.

1. 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 한다.

2. 이전에 등장했던 단어는 사용할 수 없다.

3. 한 글자인 단어는 인정 되지 않는다.

 

가장 먼저, 3번 조건에 대해서 이야기를 하고 싶다. 문제에서 제시한 끝말잇기 규칙 중 5번에 해당하는 규칙이다.

한 글자인 단어는 인정이 되질 않는다고 되어있다. 그런데 ! 문제의 제한사항에 보면, "단어의 길이는 2이상 50이하입니다" 라고 되어 있다. 그래서 본인은 이부분에 대해서 고민을 조금 했었다.

한 글자인 단어는 인정이 되질 않는데, 우리에게 주어지는 단어들은 2글자 이상이라는 것이 조금은 이해가 잘 되질 않아서 고민을 좀 했었다.. 결국 조금은 찝찝하지만 "한 글자인 단어는 인정되지 않는다" 라는 조건을 배제하고 풀었더니 통과를 할 수 있었다.

그러니, 위의 조건은 무시하고 넘어가도록 하자.

 

1. 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 한다.

먼저 이 조건을 처리하는 방법부터 이야기를 해보자.

말 그대로, 앞 사람이 말한 단어의 마지막 문자를 기억하고 있으면 된다. 즉 ! 이를 저장해둘 변수가 하나 필요하다.

본인은 char형의 'Before' 이라는 변수를 만들어서 이 변수에 앞 사람이 말한 단어의 마지막 문자를 계속해서 저장해주었다.

 

2. 이전에 등장했던 단어는 사용할 수 없다.

문자열로 주어지는 단어들에 대한 중복 탐색이 필요한 과정이다.

본인은 이를 위해서 자료구조 map을 사용해 주었다. map<string , bool> 의 식으로 선언을 한 후에 주어진 문자열이 기존에 나온적이 있다면 true를, 없다면 false 라는 값을 가지도록 구현해 주었다.

만약, 말하고 있는 단어가 이미 true로 설정되어 있는 상태라면, 기존에 나온 적 있는 문자열이라는 것을 의미하므로 그대로 탈락 한다고 판단해 주었다.

 

#2. 정답도출

우리는 결국 몇 번 사람이 몇 번째에 탈락을 하는지 구해야 한다. 탈락자가 없을 수도 있다.

이를 위해서 3개의 변수를 통해서 정답을 도출해 주었다.

1. 끝말잇기에 사용하는 단어들을(매개변수 words) 가르키는 변수

2. 사람의 번호를 나타내는 변수

3. 몇 번째인지, 즉, 현재 사람들이 몇 번 Rotate를 돌았는지를 나타내는 변수

 

1번 변수는 0번 Index부터 words의 size()만큼 증가하게 될 것이다. 중간에 누가 탈락을 해서 게임이 끝나게 되었다면, 이 변수의 값은 words의 size()보다는 작을 것이다. 하지만, 모두가 올바르게 해서 모든 단어를 다 말하였다면 이 변수의 값은 words의 size()가 될 것이다. 이를 통해서, 탈락한 사람이 있는지 없는지를 판단해 주었다.

 

2번 변수는 사람의 번호를 나타내는 변수이다. 1번 변수가 증가할 때 마다 이 변수 또한 하나씩 증가하게 될 것이다. 하지만 ! 이 변수의 값이 N(게임에 참여한 사람의 수) 보다 커지게 되면 다시 1로 초기화를 시켜주었다. 왜냐하면 모든 사람들이 다 한턴을 돌았다면 다시 1번으로 돌아가기 때문이다.

 

3번 변수는 몇 번째인지를 나타내는 변수이다. 2번 변수가 1로 초기화되는 시점에 1씩 증가하는 변수이다.

이를 통해서 몇 번째, 즉, 몇번 Rotate를 돌았는지를 판단해 주었다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
using namespace std;
 
vector<int> solution(int n, vector<string> words)
{
    map<string, bool> Visit;
    vector<int> answer;
    int Number = 1;
    int Rotate = 1;
    int Idx = 0;
    char Before;
    while (Idx < words.size())
    {
        if (Idx == 0)
        {
            Before = words[0][words[0].length() - 1];
            Visit[words[0]] = true;
        }
        else
        {
            if (words[Idx][0] == Before)
            {
                if (Visit[words[Idx]] == false)
                {
                    Visit[words[Idx]] = true;
                    Before = words[Idx][words[Idx].length() - 1];
                }
                else break;
            }
            else break;
        }
 
        Number++;
        if (Number > n)
        {
            Number = 1;
            Rotate++;
        }
        Idx++;
    }
    if (Idx == words.size())
    {
        answer.push_back(0);
        answer.push_back(0);
        return answer;
    }
    answer.push_back(Number);
    answer.push_back(Rotate);
    return answer;
}