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

풀이

N명의 순서대로 영어 끝말잇기를 진행하는데, 모두 올바른 답을 했다면 [0, 0]을 리턴하고, 아니라면

틀린 사람의 번호와 몇 번째로 틀렸는지를 리턴하면 된다.

 

문제를 쪼개서 해결해보자.

한 번 말했던 단어는 다시 등장하면 안 된다. 어떻게 체크할까?

여러 가지 방법이 있지만 et 자료구조를 이용하면 쉽게 중복을 체크할 수 있다.

s.find(words[i]) != s.end()
-> 조건을 만족한다면 아직 해당 단어는 처음 등장한 단어다.
-> 조건을 만족하지 못한다면 이미 전에 등장했던 단어를 의미한다.

 

사람의 번호 사이클은 어떻게 구할까?

그 사람이 말했던 단어는 몇 번째로 틀렸을까?

n = 3이라고 하면, mod 연산을 이용하면 쉽게 구할 수 있다.

person = index % n;

cycle = index  / n;

index	0	1	2	3	4	5	6	7	8
person	0	1	2	0	1	2	0	1	2
cycle	0	0	0	1	1	1	2	2	2

주의할 점은 사람의 번호는 1번부터 시작하므로 마지막에 각각 +1씩 해야 된다.

 

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer(2, 0);
    int person_num = 0;
    set<string> s;
    string previous;
    for(int i = 0; i < words.size(); i++) {
        person_num = i % n;
        if(previous == "") previous = words[i];
        else if(previous.back() != words[i].front() || s.find(words[i]) != s.end()) {
            answer[0] = person_num + 1;
            answer[1] = i / n + 1;
            break;
        }
        s.insert(words[i]);
        previous = words[i];
    }
    return answer;
}