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

영어 끝말잇기

문제 링크

영어 끝말잇기

분석

영어 끝말잇기의 규칙은 다음과 같습니다.

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

모든 단어는 알파벳 소문자로 이루어져 있습니다.

가장 먼저 탈락하는 사람의 번호와 몇 번째 차례에서 탈락하는지 반환해야합니다.
첫 인덱스에 번호, 두 번째 인덱스에 차례 형태를 가져야합니다.
만약, 탈락자가 없는 경우 [0, 0]으로 반환해야합니다.

매 차례 확인해야하는 것은 다음과 같습니다.

• 앞 사람이 말한 단어의 마지막 글자로 시작했는가
• 이전에 등장한 적 없는 단어를 사용했는가

풀이

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer(2, 0);
    
    // 사용한 글자를 저장하기 위한 자료구조
    unordered_set<string> usedWords;

    // 현재 차례의 시작 단어를 저장하기 위한 변수
    // 첫 시작에서는 첫 시작 글자와 같도록 설정한다.
    char prev_char = words[0][0];
    
    // 끝말잇기 단어 순회
    for (int i = 0; i < words.size(); ++i)
    {
        // 이미 나온 단어이거나 이전 단어의 마지막 글자와 다른 경우
        if (usedWords.find(words[i]) != usedWords.end() ||
           prev_char != words[i][0])
        {
            // i는 0-based이므로, 1-based를 기준으로 연산해준다.
            answer[0] = i % n + 1;
            answer[1] = i / n + 1;
            break;
        }
        
        prev_char = words[i].back();
        usedWords.insert(words[i]);
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(m)$입니다.

• 단어를 순회하는 반복문 $O(m)$
• unordered_set의 삽입 속도, $O(1)$
  • 해시 충돌로 인한 최악은 $O(m)$이지만, 일반적으로 1로 취급합니다.

공간 복잡도는 $O(m)$입니다.

• 사용한 글자를 저장하기 위한 usedWords $O(m)$

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 3.67MB)
테스트 2 〉 통과 (0.02ms, 3.66MB)
테스트 3 〉 통과 (0.01ms, 4.19MB)
테스트 4 〉 통과 (0.02ms, 3.65MB)
테스트 5 〉 통과 (0.02ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 4.18MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.02ms, 4.25MB)
테스트 10 〉 통과 (0.02ms, 4.25MB)
테스트 11 〉 통과 (0.02ms, 4.16MB)
테스트 12 〉 통과 (0.02ms, 4.11MB)
테스트 13 〉 통과 (0.02ms, 4.18MB)
테스트 14 〉 통과 (0.01ms, 4.11MB)
테스트 15 〉 통과 (0.02ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.06MB)
테스트 17 〉 통과 (0.01ms, 4.19MB)
테스트 18 〉 통과 (0.02ms, 4.12MB)
테스트 19 〉 통과 (0.01ms, 4.21MB)
테스트 20 〉 통과 (0.03ms, 4.14MB)