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

문제

영어 끝말잇기 : 문제 링크

문제 분석

• 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있다. 영어 끝말잇기는 다음과 같은 규칙으로 진행된다.

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

• 다음은 3명이 끝말잇기를 하는 상황을 나타낸다.

tank → kick → know → wheel → land → dream → mother → robot → tank

• 위 끝말잇기는 다음과 같이 진행된다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말한다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말한다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말한다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말한다.
• (계속 진행)

• 끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 된다. 사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성

• 제한 사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수이다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하이다.
• 단어의 길이는 2 이상 50 이하이다.
• 모든 단어는 알파벳 소문자로만 이루어져 있다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않아도 된다.
• 정답은 [ 번호, 차례 ] 형태로 return
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return

• tmp 내에 words의 원소가 존재하는지 확인하기 위해 find() 함수를 사용하므로 algorithm 헤더를 include
• 가장 먼저 탈락하는 사람의 번호와 몇 번째 차례에 탈락하는지를 저장할 정수형 벡터 answer과 words의 원소를 순서대로 저장할 문자열형 벡터 tmp를 초기화. words의 첫번째 원소를 tmp에 저장하고, for loop를 통해 words의 두번째 원소부터 마지막 원소까지 순환. if문과 find() 함수를 사용하여, 1) words의 현재 인덱스 단어가 tmp에 존재하는지 확인하여 있는경우 또는 2) tmp의 마지막 원소의 마지막 문자와 words의 현재 인덱스 단어의 첫번째 문자가 다르다면 answer에 i % + 1(가장 먼저 탈라하는 사람의 번호)과 i / n + 1(몇 번째 차례에 탈락하는지 번호)을 순서대로 저장하고 answer을 return. if문을 성립하지 않는다면 words의 현재 인덱스 단어를 tmp에 저장. loop를 탈출 했다면 탈락자가 없음을 의미하므로 [0, 0]을 return

1. vector내에 해당 원소가 존재하는지 확인
=> find(v.begin(), v.end(), 찾을 대상)
1) return 값이 v.end()인 경우 => 해당 원소가 존재하지 않음
2) return 값이 v.end()가 아닌 경우 => 해당 원소가 존재함
2. vector내에서 해당 원소가 위치하는 인덱스 찾기
=> find(v.begin(), v.end(), 찾을 대상) - v.begin

풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    vector<string> tmp;
    
    tmp.push_back(words[0]);
    for(int i = 1; i < words.size(); ++i) {
        if(find(tmp.begin(), tmp.end(), words[i]) != tmp.end() || tmp.back().back() != words[i][0]) {
            answer.push_back(i % n + 1);
            answer.push_back(i / n + 1);
            return answer;
        }
        tmp.push_back(words[i]);
    }
    return {0, 0};
}