프로그래머스 (Level 2) : 영어 끝말잇기 /C++, map (해쉬, 딕셔너리)

문제

프로그래머스

 

input : n (끝말잇기를 하는 사람 수), words (끝말잇기 단어 문자열배열)

output : [가장 먼저 탈락한 사람번호, 탈락한 게임 순서]

 

 

입출력 예

input		output
n	words	result
3	["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]	[3,3]
5	["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"]	[0,0]
2	["hello", "one", "even", "never", "now", "world", "draw"]	[1,3]

 

입출력 예 설명 (출처 : 프로그래머스)

입출력 예 #1  (n=3 : 3명의 사람)
1번 사람 : tank, wheel, mother
2번 사람 : kick, land, robot
3번 사람 : know, dream, tank
3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로

3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다. ->  [3, 3] return

입출력 예 #2 (n=5 : 5명의 사람)
1번 사람 : hello, recognize, gather
2번 사람 : observe, encourage, refer
3번 사람 : effect, ensure, reference
4번 사람 : take, establish, estimate
5번 사람 : either, hang, executive
이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. ->  [0, 0] return

입출력 예 #3 (n=2 : 2명의 사람)
1번 사람 : hello, even, now, draw
2번 사람 : one, never, world
1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다. ->  [1, 3] return

 

 

풀이

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

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    map <string,int> m;
    int cnt=0;
    
    for(int i=0;i<words.size();i++){
        if(i%n==0)cnt++; //차례 count
        
        if(i>0){
            int prewordln = words[i-1].length()-1;
            if(words[i-1][prewordln]!=words[i][0]){ //끝말잇기를 틀렸을때
                answer.push_back((i+1)-n*(cnt-1));
                answer.push_back(cnt);            
                return answer;
            }
        }
        
        if(m.find(words[i])!=m.end()){ //이미 말했던 단어일때
            answer.push_back((i+1)-n*(cnt-1));
            answer.push_back(cnt);            
            return answer;
        }
        else m.insert({words[i],1}); //처음 나온 단어 딕셔너리 추가
    }
    if(answer.empty()) return {0,0}; //탈락자가 없을때
}

 

탈락 기준

1. 끝말잇기가 틀린 경우

2. 이미 말했던 단어인 경우

 

처음 등장하는 단어는 key:value 구조(딕셔너리)인 map에 저장했다.

탈락자가 발생하는 경우에 탈락한 사람의 번호와 탈락한 게임순서를 return 해야한다.

 

cnt (게임순서)	0			1			2
i	0	1	2	3	4	5	6	7	8
i+1	1	2	3	4	5	6	7	8	9
사람번호	1	2	3	1	2	3	1	2	3

 

게임순서는 i%n==0 인 경우마다 count

사람번호는 게임순서와 문자열 순서와의 연관을 고려하여 (i+1)-n*(cnt-1) 로 계산하였다.

 

 

 

---

 

 

C++ map (key:value 딕셔너리 자료구조)

 

*map.find(key) = key 를 찾지 못하면 map.end()를 return 한다.

map에서 특정 키를 찾고 싶을때 if(map.find(key)!=map.end()) 사용

 

 

- map 사용법 참고

[C++] map container 정리 및 사용법

 

[C++][STL] map 사용법 정리