영어 끝말잇기

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12981

❔ 문제 설명

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

① 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.

② 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.

③ 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.

④ 이전에 등장했던 단어는 사용할 수 없습니다.

⑤ 한 글자인 단어는 인정되지 않습니다.

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

⚠️ 제한사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.

• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.

• 단어의 길이는 2 이상 50 이하입니다.

• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.

• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.

• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.

• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

---

💡 풀이 (언어 : Java & Python)

Java

public class Solution {
    public int[] solution(int n, String[] words) {
        // 중복 체크할 Set
        HashSet<String> set = new HashSet<>();
        // 처음 단어의 끝 글자, set에 첫 단어 넣기
        char last = words[0].charAt(words[0].length()-1);
        set.add(words[0]);
        // 두번째 단어부터 시작
        for (int i = 1; i < words.length; i++) {
            // 끝말잇기에 실패하거나, 중복단어를 말한 경우
            if (words[i].charAt(0) != last || !set.add(words[i]))
                return new int[]{i % n + 1, i / n + 1};
            // 끝 글자 갱신
            last = words[i].charAt(words[i].length()-1);
        }
        return new int[] {0, 0};
    }
}

Python

def solution(n, words):
    # 탈락자 없이 words 다 돌면 [0, 0] 반환하도록 초기화
    answer = [0, 0]
    
    # set 이용해서 중복을 제거 하고 다시 리스트로 변환
    uni_words = list(set(words))
    
    # {단어 : 0(횟수)} 형태의 딕셔너리
    check = {uni_words[i] : 0 for i in range(len(uni_words))}
    
    # 차례
    turn = 1

    # 첫 단어는 반복문에서 예외이므로 여기서 처리
    # 전 순서 단어의 끝말 (첫 단어의 끝말로 시작)
    last_word = words[0][-1]
    
    # 첫 단어 check에 등록하고 한번 카운트
    check[words[0]] = 1

    for i in range(1, len(words)):
        # 차례 카운트
        if i % n == 0:
            turn += 1 
        
        # 끝말잇기 실패 or 같은 단어가 이미 한 번 나왔을 경우 종료
        if words[i][0] != last_word or check[words[i]] == 1:
            # 그 사람의 번호 = 해당 인덱스 사람수로 나눈 나머지 값 + 1
            answer[0] = (i % n) + 1
            answer[1] = turn
            break
        
        # 끝말잇기 성공시 check 딕셔너리에 성공 단어 등록 및 횟수 갱신
        else:
            last_word = words[i][-1]
            check[words[i]] += 1

    return answer