[Porgrammers] 영어 끝말잇기

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

프로그래머스

0. Headers

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

 

1. 알고리즘

 - 단어 배열에 값을 넣기 위해 strAnswer 생성 및 단어를 확인하기 위해 rightString 생성

 - 누가 말한 사람인지 몇번 째로 말했는 지 확인하기 위해 number, numberMax 확인

vector<int> solution(int n, vector<string> words) {
    vector<int> answer; // 정답 배열
    vector<string> strAnswer; // 단어 배열
    strAnswer.push_back(words[0]); // 첫번째 단어 제외하기 위해 추가
    
    string rightString = words[0]; // 다음 단어가 맞는 지 확인
    int number = 0; // 누가 말했는지
    int numberMax = 0; // 몇번 쨰 말했는지
    bool start = true; // 첫 번째 반복 제외
}

 - 처음 값을 넣은 값은 제외 및 다음 반복문 시작

 - 몇번 째 사람인지 알기 위해 number 값을 구하고 몇번 말했는지 알기 위해 numberMax를 구함

 - 종료 조건

   - 마지막 단어가 첫번째 단어가 맞는 지 확인

   - find를 통해 같은 값이 있는 지 확인

   - 끝말 잇기가 제대로 종료

 - strAnswer에 확인한 단어 추가 및 마지막 단어를 확인하기 위한 rightString 확인

vector<int> solution(int n, vector<string> words) 
{
    for (string str : words)
    {
        if (start) {start = false; continue;} // 첫번 째 값 제외
        
        number = (number + 1) % n; // 몇번 째 사람인지
        numberMax++; // 몇번 말했는지
        
        if (rightString[rightString.length() - 1] != str[0]) break; // 마지막 단어가 첫번째 단어가 맞는 지 확인
        if (find(strAnswer.begin(), strAnswer.end(), str) != strAnswer.end()) break; // find를 통해 같은 값이 있는 지 확인
        
        strAnswer.push_back(str);
        rightString = str;
        
        if (words[words.size() - 1] == str) return vector<int>{0,0}; // 끝말 잇기가 제대로 종료
    }
}

 - answer 값에 몇번 째 사람인지 몇번 말했는지 확인

vector<int> solution(int n, vector<string> words) 
{
    answer.push_back(number + 1);
    answer.push_back(numberMax / n + 1);
    
    return answer;
}

 

2. 완성 코드

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

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    vector<string> strAnswer;
    strAnswer.push_back(words[0]);
    string rightString = words[0];
    int number = 0;
    int numberMax = 0;
    bool start = true;
    
    for (string str : words)
    {
        if (start) {start = false; continue;}
        
        number = (number + 1) % n;
        numberMax++;
        
        if (rightString[rightString.length() - 1] != str[0]) break;
        if (find(strAnswer.begin(), strAnswer.end(), str) != strAnswer.end()) break;
        
        strAnswer.push_back(str);
        rightString = str;
        
        if (words[words.size() - 1] == str) return vector<int>{0,0}; // 종료 조건
    }
    answer.push_back(number + 1);
    answer.push_back(numberMax / n + 1);
    
    return answer;
}

Test Code