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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

단어들을 순회하면서 해당 단어가 조건에 맞지 않는다면, [해당 단어를 말한 사람, 그 사람이 자신의 몇 번째에 탈락하는지]를 리턴하는 문제이다. 

 

끝말잇기를 진행하는 총 사람의 수가 n명일 떄, words를 순회하는 인덱스 i에 대하여, 

i번째 단어는 i%n+1번째 사람이 말하고, 그 사람은 i/n+1 번째로 단어를 말하는 중이다. (인덱스는 0부터 시작하므로 몫과 나머지 계산에 각각 1을 더해준다.)

 

단어를 순회하면서, 

1. 단어의 길이가 1인 경우

2. 해당 단어가 이전 단어의 끝글자로 시작하지 않는 경우,

3. 이미 중복된 경우

[i%n+1, i/n+1]을 리턴하면 정답이다.

 

단어가 중복되는지 확인할 때는 해시 자료구조인 unordered_set을 활용하면 O(1)에 원소를 삽입/조회 할 수 있다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<int> solution(int n, vector<string> words) {

    unordered_set<string> st;

    for (int i=0; i<words.size(); i++) {
        int p = i%n+1;
        int o = i/n+1;    
        if (words[i].size() == 1) return {p, 0}; //1글자일 때
        if (i != 0 && words[i-1].back() != words[i][0]) return {p, o}; //전 단어의 끝글자로 시작하지 않을 때
        if (st.find(words[i]) != st.end()) return {p, o}; //중복된 단어일 때
        st.insert(words[i]);
    }
    return {0, 0};
}