[프로그래머스] Lv.2 영어 끝말잇기 c++

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

프로그래머스

 

n명의 사람들이 영어 끝말잇기를 합니다. 규칙은 다음과 같습니다:

1. 순서대로 단어를 말하고, 마지막 사람이 말한 후 다시 1번부터 시작합니다.
2. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
3. 이전에 말했던 단어는 사용할 수 없고, 한 글자인 단어는 인정되지 않습니다.

탈락 조건:

• 이미 말한 단어를 다시 말했거나,
• 앞 단어의 마지막 글자로 시작하지 않는 단어를 말했을 때.

입력으로 n(사람 수)과 단어 배열 words가 주어질 때, 가장 먼저 탈락한 사람의 번호와 차례를 반환합니다.

탈락자가 없으면 [0, 0]을 반환합니다.

 

풀이 방법

생각보다 stage와 order 계산이 헷갈려서 시간이 오래 걸렸던 문제입니다.

순서를 반복할 때는 모듈러 연산(%)을 활용하면 효율적으로 해결할 수 있습니다.

영어 끝말잇기가 이어지려면 이전에 말한 단어의 끝 알파벳과 현재 사람이 말한 단어의 첫 알파벳이 일치해야 합니다.

 

또한, words 배열에는 중복 단어가 있을 수 있으므로, 이미 말한 단어인지도 매번 확인해야 합니다.

이를 위해 HashMap을 활용해 각 단어를 키로 등록하고, 현재 단어가 이미 등록된 단어인지 빠르게 확인할 수 있도록 했습니다.

 

배열은 1부터 시작하는 인덱스 기반으로 처리하였고, 각 단어를 이전에 말한 단어와 비교했을 때 끝말잇기 조건이 성립하지 않을 경우,해당 스테이지의 순서와 사람 번호를 반환하도록 했습니다.

만약 문제없이 끝말잇기가 종료될 경우, [0, 0]을 반환하여 탈락자가 없음을 나타냅니다.

풀이 코드

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

using namespace std;

int stage=1, order;
unordered_map<string,string> map;
vector<int> solution(int n, vector<string> words) {
    map[words[0]] = words[0]; 
    for(int i=1; i<words.size(); i++){
        order = (i%n)+1;
        if(i%n == 0) stage++;
        if(map.find(words[i]) != map.end()||words[i].front() != words[i-1].back()){
            return {order, stage};
        }
        map[words[i]] = 1;
    }
    return {0,0};
}