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

풀이 날짜 : 2025.05.08
문제 유형 : Summer/Winter Coding(~2018)
문제 제목 : 영어 끝말잇기
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12981

Intuition

• 끝말잇기 게임에서 규칙을 어긴 첫 번째 사람의 번호와 차례를 반환해야 한다. 규칙 위반은 아래와 같다.
  • 중복된 단어를 사용한 경우
  • 이전 차례에서 말한 단어의 마지막 글자와 현재 말한 단어의 첫글자가 다른 경우
• 이전의 사용한 단어를 어딘가에 저장하고, 빠르게 탐색해야 한다.
  • 중복 단어를 저장하기 전에 함수가 끝날 것이므로 배열보다 탐색이 빠른 Set이 적절할 것이다.
• 규칙을 위반한 첫 번째 사람의 번호와 차례를 계산해야 한다.
  • 현재 단어의 순서를 0부터 시작해서 i라고 하고, 인원이 n명이라고 할 때, 아래와 같이 정의할 수 있다.
    번호 = i % n + 1
    순서 = Math.floor(i / n) + 1

Approach

• 중복 단어를 저장할 Set을 선언한다.
• 번호(num)와 순서(turn)를 저장할 변수를 0으로 선언한다. (탈락자가 생기지 않으면 0으로 반환하기 위해)
• set에 첫 번째 단어를 추가한다.
• 1번 인덱스부터 words를 for 루프로 순회한다.
  • 두 가지 규칙을 하나라도 위반했다면 번호와 순서를 계산하여 변수에 저장하고 for 루프를 종료한다.
    • 중복된 단어를 사용한 경우
    • 이전 차례에서 말한 단어의 마지막 글자와 현재 말한 단어의 첫글자가 다른 경우
  • 규칙을 위반하지 않았다면 set에 단어를 추가한다.
• 번호와 순서를 배열로 반환한다.

Complexity

• Time complexity : O(w)
  • words의 길이를 w라고 할 때 for 루프에서 최대 words의 길이만큼 순회하므로 O(w)이다.
• Splace complexity : O(w)
  • words의 길이를 w라고 할 때 단어의 중복이 없다면 Set에 최대 words의 길이만큼 저장할 수 있다.
  • 각 단어의 길이가 2~50이라는 조건이 있으므로 이는 상수 범위로 취급하고, 종합적으로 O(w)이라고 볼 수 있다.

Code (JS)

function solution(n, words) {
    const set = new Set();
    let num = 0;
    let turn = 0;

    // 첫 번째 요소 넣고 시작
    set.add(words[0]);

    for (let i = 1; i < words.length; i++) {        
        const isDuplicate = set.has(words[i]);
        const isWrong = words[i - 1].at(-1) !== words[i][0];

        if (isDuplicate || isWrong) {
            num = i % n + 1;
            turn = Math.floor(i / n) + 1;
            break;
        }

        set.add(words[i]);
    }

    return [num, turn];
}