[c++] 프로그래머스 - 영어 끝말잇기(Level 2)

문제

코딩테스트 연습 - 영어 끝말잇기

 

코드

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;


vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    map<string,int> duplicate;
    int cycle = 1;
    char before_char = words[0].back();
    duplicate[words[0]]++;

    for(int i=1; i<words.size(); i++){
        if(i%n==0) cycle++;

        if(words[i].front()!=before_char){
            answer.push_back((i%n)+1);
            answer.push_back(cycle);
            return answer;
        }

        if(duplicate[words[i]]!=0){
            answer.push_back((i%n)+1);
            answer.push_back(cycle);
            return answer;
        }
        before_char = words[i].back();
        duplicate[words[i]]++;

    }

    if(answer.size()==0){
        answer.push_back(0);
        answer.push_back(0);
    }

    return answer;
}

 

풀이

문제를 먼저 설명하자면 n명의 사람이 영단어로 끝말잇기를 진행하는데 끝말을 이어가지 못하거나 이전에 사용했던 단어를 사용하면 끝나게 되고 그때 틀린 사람의 번호와 몇 번째 사이클 때 틀렸는지 출력하는 문제입니다.

단순하게 O(N)시간 복잡도로 이번 단어의 첫 글자가 이전 단어의 끝 글자와 맞는지 조건문으로 판별하였고, Map 테이블을 사용하여 중복 판단을 하여 해당 조건에 걸릴 경우 끝말잇기가 끝난 경우이기 때문에 answer 벡터에 추가하고 return 했습니다. answer 벡터의 사이즈가 0 인 경우는 전부 다 올바르게 끝말잇기를 진행했기 때문에 아무것도 들어있지 않는 상태이기에 0을 직접 삽입해주어 출력했습니다.