Programmers | Level 2 | 영어 끝말잇기

Programmers | Level 2 | 영어 끝말잇기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Simulation

Description

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

1. 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
2. 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
3. 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
4. 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
5. (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

Constraints

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [번호, 차례] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

Examples

n	words	result
3	["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]	[3, 3]
5	["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"]	[0, 0]
2	["hello", "one", "even", "never", "now", "world", "draw"]	[1, 3]

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(n)

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        // 사용된 단어를 추적하기 위해 HashSet을 사용합니다.
        Set<String> usedWords = new HashSet<>();
        // 첫 번째 단어는 미리 집합에 추가합니다.
        usedWords.add(words[0]);
        
        for (int i = 1; i < words.length; i++) {
            int player = (i % n) + 1; // 현재 말을 하고 있는 사람의 번호
            int turn = (i / n) + 1;   // 현재 사람의 차례
            
            String prevWord = words[i - 1];
            String currentWord = words[i];
            
            // 현재 단어가 이미 사용되었거나, 앞 단어의 마지막 문자와 현재 단어의 첫 문자가 일치하지 않으면
            if (usedWords.contains(currentWord) || prevWord.charAt(prevWord.length() - 1) != currentWord.charAt(0)) {
                return new int[] {player, turn};
            }
            
            // 사용된 단어 목록에 현재 단어를 추가합니다.
            usedWords.add(currentWord);
        }
        
        // 모든 단어를 사용했는데 탈락자가 없다면 [0, 0]을 반환합니다.
        return new int[] {0, 0};
    }
}

Approaches

이 문제는 영어 끝말잇기 게임의 규칙을 시뮬레이션하여 첫 번째로 탈락하는 사람을 찾는 문제입니다. 각 사람은 차례대로 단어를 말하고, 이전 단어의 마지막 글자로 시작하는 단어를 사용해야 하며, 이전에 사용된 단어를 반복해서는 안 됩니다. 이 규칙들을 정확히 구현하는 것이 문제 해결의 핵심입니다.

끝말잇기 게임에서 주의해야 할 주요 규칙은 다음과 같습니다:

• 중복 단어 금지: 이전에 등장한 단어는 다시 사용할 수 없습니다.
• 단어 연결 규칙: 앞사람이 말한 단어의 마지막 글자로 시작하는 단어를 말해야 합니다.

이를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

• 단어 사용 여부 확인:
  • 사용된 단어를 추적하기 위해 Set<T>을 사용합니다. Set<T>은 데이터의 삽입과 검색이 평균 O(1) 시간 복잡도를 가지므로 효율적입니다.
  • 각 사람이 단어를 말할 때마다 그 단어가 이전에 사용되었는지 집합을 통해 확인합니다. 만약 이미 사용된 단어라면 그 사람이 탈락한 것으로 간주합니다.
• 마지막 문자와 첫 문자 확인:
  • 각 단어의 마지막 문자와 다음 단어의 첫 문자를 비교하여 규칙이 지켜지는지 확인합니다.
  • 만약 앞 사람의 단어 마지막 문자와 현재 사람의 단어 첫 문자가 일치하지 않는다면 규칙을 어긴 것으로 간주하고 그 사람이 탈락한 것으로 처리합니다.
• 탈락자 번호 계산:
  • 탈락자가 발생하면 해당 사람의 번호를 반환해야 합니다.
  • 사람의 번호는 (i % n) + 1로 계산할 수 있습니다. 여기서 i는 단어의 인덱스입니다. 이는 0부터 시작하는 인덱스를 n명의 순서로 맞추기 위해서입니다.
  • 예를 들어, 3명의 사람들이 차례로 단어를 말하는 경우, i가 0일 때 1번 사람, i가 1일 때 2번 사람, i가 2일 때 3번 사람이 단어를 말합니다. 그 다음 i가 3이 되면 다시 1번 사람이 단어를 말하게 됩니다. 이를 일반화하면 i % n + 1로 현재 말을 하는 사람의 번호를 계산할 수 있습니다.
• 탈락자 차례 계산:
  • 차례는 (i / n) + 1로 계산할 수 있습니다. 여기서 i는 단어의 인덱스입니다. 이는 각 사람의 차례가 몇 번째인지 계산하기 위해서입니다.
  • 예를 들어, 첫 번째 차례에서는 i가 0, 1, 2일 때 각각 1번, 2번, 3번 사람이 단어를 말합니다. 두 번째 차례에서는 i가 3, 4, 5일 때 각각 1번, 2번, 3번 사람이 단어를 말합니다. 이를 일반화하면 i / n + 1로 현재 사람의 차례를 계산할 수 있습니다.
• 탈락자 없이 게임 종료 처리:
  • 모든 단어를 사용했는데 탈락자가 발생하지 않으면 [0, 0]을 반환합니다. 이는 주어진 단어들로 끝말잇기가 정상적으로 종료된 경우를 의미합니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다. 이는 주어진 문제를 효율적으로 해결하는 데 충분합니다.