[프로그래머스] Lv. 2 영어 끝말잇기 (C++)

최초 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

    // x: 탈락 지점 인덱스
    int x = 0;
    bool failed = false;
    for (size_t i = 1; i < words.size(); i++) {
        // 지금 단어의 첫 글자가 이전 단어의 끝 글자인지 확인
        if (words[i-1].back() != words[i].front()) {
            x = i;
            break;
        }
        // 지금 단어가 이전 단어 중에 등장한 적이 없는지 확인
        for (size_t j = 0; j < i; j++) {
            if (words[j] == words[i]) {
                x = i;
                failed = true;
                break;
            }
        }
        if (failed) break;
    }
    // x == 0이라면 탈락 지점이 발생하지 않았다는 의미이다.
    if (x == 0) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(x%n + 1);
        answer.push_back(x/n + 1);
    }

    return answer;
}

• 이중 for문에서 탈출할 때, 플래그를 설정하여 탈출하는 법을 배웠다.
  • for문 밖에서 bool 타입의 플래그를 설정해둔다.
  • 내부 for문에서 특정 조건이 충족되면 플래그를 변경한다.
  • 외부 for문에서는 내부 for문이 종료될 때마다 플래그가 변경되었는지 확인한다.

다만, 버전 1에서는 등장한 적이 있는 단어를 검사하기 위해 이전 단어들을 모두 훑는 $O(n^2)$ 방식이었다. 왜냐하면 각 n번째 단어에 대해 n-1번째 단어까지를 모두 검사해야하기 때문이다.

중복 여부를 검사할 때 사용하면 좋은 것이 unorderd set이다. unorderd set은 중복 여부를 $O(1)$ 수준으로 검사할 수 있다. 왜냐하면 내부적으로 entity를 hash table에 저장하기 때문이다.

변경 전

for (size_t j = 0; j < i; j++) {
    if (words[j] == words[i]) {
        x = i;
        failed = true;
        break;
    }
}

변경 후

if (used.count(words[i])) {
    x = i;
    failed = true;
    break;
}

최종 버전

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    unordered_set<string> used; // 사용된 단어들을 담을 변수
    used.insert(words[0]); // 첫 단어는 어떤 경우에도 실패할 수 없으므로 검사하지 않고 바로 사용된 단어에 넣는다.
    for (int i = 1; i < words.size(); i++) {
        if (words[i-1].back() != words[i].front() || // 현재 단어의 첫 글자가 이전 단어의 마지막 글자와 일치하는지 확인한다.
            used.count(words[i])) // 현재 단어가 이전에 등장한 적이 없는지 확인한다.
            return {i%n + 1, i/n + 1}; // 둘 중 하나라도 만족하지 못한다면 현재 인덱스 i가 첫 오답이 발생한 인덱스이다.
        used.insert(words[i]); // 모두 만족한다면 현재 단어도 사용된 단어에 담는다.
    }
    return {0, 0}; // 모든 단어를 순회하며 문제가 없다면, (0, 0)을 반환한다.
}