[프로그래머스] 2단계 - 영어 끝말잇기

문제 설명

n명의 사람이 영어 끝말잇기를 하고 있을때, 이전에 등장했던 단어를 말하거나 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말하지 않았을때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 몇 번째 차례에 탈락하는지 return

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

프로그래머스

 

문제 풀이법

영어 단어가 들어있는 vector를 순회하면서

1. 앞에서 말한 단어가 또 나왔는지 검사

2. 앞에서 말한 단어의 마지막 말로 시작하는지 검사

총 2가지를 검사하면 된다

 

바깥쪽의 for문은 인덱스 1부터 단어 vector의 끝까지 순회하며, 앞에서 말한 단어의 마지막 말로 시작하는지 검사한다

안쪽의 for문은 지금까지 나왔던 단어인지 아닌지 검사한다

 

만일 2개의 조건 중에 하나라도 걸렸다면 가장 먼저 탈락하는 사람의 번호는 (i % n) + 1로 구할 수 있다

그 사람이 몇 번째 차례에서 탈락하는지는  (i / n) + 1로 구할 수 있다

여기서 n은 주어진 사람의 수 이고, i는 바깥쪽 for문의 변수이며 현재 보고있는 단어 vector의 인덱스이다

인덱스는 0부터가 아닌 1부터 시작하므로 마지막에 +1 을 해주고, answer vector에 넣어 준 다음 바로 return 한다

for문을 다 돌았다면, 끝말잇기의 탈락자가 나오지 않은 것이므로 문제에서 주어진 대로 0을 push 한 뒤에 return 한다

 

소스 코드

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

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    
    for(int i = 1; i < words.size(); i++) {
        
        if (words[i - 1][words[i - 1].size() - 1] != words[i][0]) {
            int person = (i % n) + 1;
                int idx = (i / n) + 1;
                answer.push_back(person);
                answer.push_back(idx);
                return answer;
        }
        
        for(int j = 0; j < i; j++) {
            if (words[i] == words[j]) {
                int person = (i % n) + 1;
                int idx = (i / n) + 1;
                answer.push_back(person);
                answer.push_back(idx);
                return answer;
            }
        }
    }

    answer.push_back(0);
    answer.push_back(0);
    return answer;
}