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

 

Level.2 

 

문제

• 구해야 하는 값 : [가장먼저 탈락하는 사람의 번호, 자신의 몇 번째 차례에 탈락하는지]

 

풀이

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer = {0,0};
    map<string, int> map;
    string word = words[0];
    map[word]++;
    int index;
    for(index=1; index<words.size(); index++){
        if(word[word.size()-1] == words[index][0]){
            word = words[index];
            map[word]++;
            if(map[word] > 1){
                break;
            }
        }
        else break;
    }
    if(index!=words.size()){
        answer[0] = index%n+1;
        answer[1] = index/n+1;
    }
    return answer;
}

• n : 게임에 참가한 사람 수
• words : 끝말잇기 게임 진행 배열 

해결방법

0. key값이 string인 배열을 사용하기 위해 자료구조 map을 활용하였다. 

1. words 배열을 순회한다.

    1-1. 끝말잇기 규칙에 맞지 않으면 반복문을 종료한다.

    1-2. 끝말잇기 규칙이 맞을 때마다 map 자료구조해 해당 단어를 집어넣는다. 같은 단어가 반복되어 사용되는지를 확인하기 위함이다.

            같은 단어를 두 번 사용했을 경우 반복문을 종료한다. 

2. words를 끝까지 순회하지 못했을 경우, 중간에 게임이 끝났다는 의미이므로 [가장 먼저 탈락하는 사람의 번호, 자신의 몇 번째 차례에 탈락하는지]를 구한다. 

 

 

 

---

 

다른 사람 풀이

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;

vector<int> solution(int n, vector<string> words) {
    int len=words.size();
    map<string,int> h;
    h[words[0]]=1;
    for(int i=1;i<len;i++)
    {
        int len1=words[i-1].size();
        if(h[words[i]] || (words[i-1][len1-1]!=words[i][0]))
            return {i%n+1,i/n+1};
        else
            h[words[i]]=1;
    }
    return {0,0};
}

쓸데없는 변수를 사용하지 않아 코드가 매우 간결하다! 

 

 

 

 

---

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

프로그래머스