[C++] Programmers Lv. 2 "영어 끝말잇기"

🔵 문제 링크

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

프로그래머스

 

🔵 신경 써야 할 점

• return {사람 번호, 몇 번째 턴}
• 현재 몇 번째 턴인지
• 아무도 탈락하지 않을 때 예외
• 끝말잇기를 제대로 안 했을 때 

위 사항을 신경써서 그대로 구현한다.

 

💡 Point

1. "단어 - bool" 쌍인 map을 만들어 현재 단어가 쓰였는지 확인한다. (set을 사용하여 중복을 처리할 수도 있다.)
2. string.rbegin()을 이용하여 문자열의 마지막 문자를 쉽게 가져올 수 있다.

 

🔵 코드

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

using namespace std;

// 신경 써야 할 것 - > return {사람 번호, 몇 번째 턴}
// 1. 현재 몇 번째 턴인지
// 2. 아무도 탈락하지 않을 때 예외
// 3. 끝말잇기를 제대로 안 했을 때 

// map (단어 - bool) 로 현재 단어 사용했는지 확인?

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    unordered_map<string, bool> isUsed;
    auto prevLast = words[0].rbegin();
    isUsed[words[0]] = true;

    for (int i = 1; i < words.size(); i++)
    {
        // 몇 번째 사람 차례인지
        int who = i % n + 1;

        // 몇 번째 턴인지
        int phase = i / n + 1;

        // 첫 번째 글자
        auto curFirst = words[i].begin();

        // 올바른 단어를 말했는가
        if (*prevLast != *curFirst || isUsed[words[i]])
        {
            answer.push_back(who);
            answer.push_back(phase);
            return answer;
        }

        // 단어 사용 처리 
        prevLast = words[i].rbegin();
        isUsed[words[i]] = true;
    }

    answer.push_back(0);
    answer.push_back(0);

    return answer;
}

 

🔵 시간 복잡도

words 벡터의 길이를 N이라 할 때, 시간 복잡도는 O(N)이다.