영어 끝말잇기

코드

[ 내 풀이 ] - algorithm의 find사용

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

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    vector<int> userCnt(n);
    char prev = ' ';
    int i=0,j=0;

    while(true)
    {
        j = j%n;
        userCnt[j]++;
        if(prev != ' '){
            /* 전체 범위가 아닌 부분에서 찾지 못한 경우 그 범위의 바로 다음 원소가 end()가 되어 반환된다 --> indx로 확인! */
            int idx = find(words.begin(), words.begin()+i, words[i]) - words.begin();
            /* 전단어의 끝이 시작과 다르거나 or 이미 말한 단어이면 아웃 */
            if(prev != words[i][0] || idx != i){
                answer.push_back(j+1);
                answer.push_back(userCnt[j]);
                break;
            }
        }
        prev = words[i][words[i].size()-1];
        i++;j++;
        if(i == words.size()){
            answer.push_back(0);
            answer.push_back(0);
            break;
        }
    }
    return answer;
}

• 깨달음
  1) <algorithm>의 find()를 사용할 때 전체 범위가 아닌 경우에서 찾을때 못찾으면
        -> v.end()가 아니라 해당 범위의 바로 다음을 의미함
  ex) find(v.begin(), v.begin()+2, str);
         :우리는 원소 2개(v.begin(), v.begin()+1)중에 str을 찾게 된다.
          하지만, 없는 경우에 v.begin()+2에 해당하는 iterator를 반환한다!
          (항상 v.end()가 아니라 현재 범위에서 다음 요소를 반환!)

---

[ 다른 풀이 ] - map 사용

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

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

• map을 사용해서 존재의 여부를 바로 파악할 수 있다!