Programmers - 영어 끝말잇기

---

title: Programmers - 영어 끝말잇기
date: 2022-07-11
tags:

• Algorithm

---

https://school.programmers.co.kr/learn/courses/30/lessons/12981

문제 요약

끝말잇기를 하는 인원수와 단어들이 주어진다. 끝말잇기가 되지 않는 단어를 말하거나, 앞에서 말한 단어가 나오면 탈락한다. 몇 번째 사람이 몇 번째 단어에서 탈락하는지 정보를 vector에 담아 return한다.

문제 풀이

구현 문제로, 단어를 순차적으로 순회하면 된다.
우선 앞에서 나온 단어와 이어지는 단어인지(끝말잇기) 확인 후, 해당 단어가 앞에서 말했던 단어인지 확인한다.
이 경우 탈락이므로 단어의 위치를 통해 몇 번째 사람, 몇 번째 단어인지 vector에 넣는다.
탈락자가 없는 경우에는 0,0을 넣어준다.

영어이기에 1 Byte로 확인이 가능하나, 2 Byte 이상의 글자일 경우 끝말잇기 확인이 어려워질 수 있다.
언어에 따라 몇 Byte인지 다르기에 언어를 확인한 후, 해당 언어가 여러 Byte에 걸쳐있다면 각 Byte별로 글자가 성립이 되는지 확인해야 한다.
여러 Byte 모두 글자가 성립이 되면, 공식 언어 사전을 이용하여 어떤 단어인지 확인하여 처리해야 한다.

프로그램

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

using std :: string ;
using std :: vector ;
using std :: unordered_map ;

vector < int > solution ( int n , vector < string > words )
{
    vector < int > answer ;
    unordered_map < string , int > umWordCheck ;
    int iSize = words.size () ;



    ++ umWordCheck [ words [ 0 ] ] ;

    for ( int i = 1 ; i < iSize ; ++i )
    {
        string strFormer = words [ i - 1 ] ;
        ++ umWordCheck [ words [ i ] ] ;

        if ( ( 2 == umWordCheck [ words [ i ] ] ) || ( strFormer [ strFormer.size () - 1 ] != words [ i ] [ 0 ] ) )
        {
            answer.emplace_back ( i % n + 1 ) ;
            answer.emplace_back ( i / n + 1 ) ;

            break ;
        }
    }

    if ( answer.empty () )
    {
        answer.emplace_back ( 0 ) ;
        answer.emplace_back ( 0 ) ;
    }


    return answer ;
}