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

문제 설명

n명의 사람이 영어 끝말잇기를 진행하고 있습니다. 규칙은 다음과 같습니다:

1. 1번부터 순서대로 단어를 말합니다. 마지막 사람이 단어를 말하면 다시 1번으로 돌아옵니다.
2. 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
3. 이미 말한 단어는 사용할 수 없습니다.
4. 한 글자 단어는 사용할 수 없습니다.

탈락 조건:

1. 앞사람이 말한 단어의 마지막 문자로 시작하지 않는 단어를 말한 경우.
2. 이전에 사용된 단어를 다시 말한 경우.

탈락자가 생긴다면, 해당 사람의 번호와 몇 번째 차례에 탈락했는지를 [번호, 차례] 형태로 반환합니다. 탈락자가 없다면 [0, 0]을 반환합니다.

---

제한 조건

1. n: 2 ≤ n ≤ 10
2. words.length: n ≤ words.length ≤ 100
3. 각 단어의 길이: 2 ≤ 단어의 길이 ≤ 50
4. 모든 단어는 알파벳 소문자로 이루어져 있습니다.

---

해결 방법

알고리즘: 해시셋(Hash Set)

1. 중복 단어 관리
   • 사용된 단어를 빠르게 확인하기 위해 Set 자료구조를 사용합니다.
   • 단어가 이미 Set에 존재하면 규칙을 위반한 것으로 간주합니다.
2. 끝말잇기 규칙 확인
   • 현재 단어의 첫 글자가 이전 단어의 마지막 글자와 다른 경우 규칙 위반입니다.
3. 순서와 차례 계산
   • 탈락한 사람의 번호는 i % n + 1, 차례는 Math.floor(i / n) + 1로 계산합니다.
4. 탈락 조건
   • Set에 단어가 이미 존재하거나, 끝말잇기 규칙을 위반한 경우 탈락자를 반환합니다.
5. 탈락자가 없을 경우
   • 모든 단어를 순회한 후에도 규칙 위반이 없으면 [0, 0]을 반환합니다.

---

시간 복잡도

1. Set 연산
   • Set.has 및 Set.add는 평균적으로 O(1)입니다.
   • words.length 만큼 순회하므로 O(n)입니다.
2. 총 시간 복잡도
   • O(n)

---

구현 코드

function solution(n, words) {
  const set = new Set();
  let lastWord = words[0][0];

  for (let i = 0; i < words.length; ++i) {
    const currentWord = words[i];

    if (currentWord[0] !== lastWord || set.has(currentWord)) {
      return [(i % n) + 1, Math.floor(i / n) + 1];
    }

    set.add(words[i]);
    lastWord = currentWord[currentWord.length - 1];
  }

  return [0, 0];
}