Skip to main content

[Java] 12981 영어 끝말잇기

📝 영어 끝말잇기

1. 문제 요약

  • [탈락자 번호, 탈락할 차례] 형태로 리턴
  • 탈락자가 없으면 [0, 0]

2. 접근 방법

1) 누적 단어 저장 어떻게 할 것인지?

  • 그동안 나온 단어를 저장하고 이미 있는 단어 나오면 탈락
  • 이 때 단어 저장 할 자료구조는? HashSet<String>

2) 탈락 조건

  • 이미 나온 단어 말함 → 아웃
  • 끝말잇기 규칙 위반(이전단어 마지막글자 != 현재 단어 첫글자) → 아웃

3) 탈락자 정보 계산

  • (탈락 단어 인덱스 % n) + 1 → 사람 번호 계산
  • (탈락 단어 인덱스 / n) + 1 → 차례 계산

3. 정답코드

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        Set<String> usedWords = new HashSet<>();
        usedWords.add(words[0]);
        
        for (int i = 1; i < words.length; i++) {
            // 끝말 맞는지 확인
            String prev = words[i - 1];
            String curr = words[i];
            
            if (usedWords.contains(curr) || prev.charAt(prev.length() - 1) != curr.charAt(0)) {
                int player = (i % n) + 1;
                int turn = (i / n) + 1;
                return new int[]{player, turn};
            }
            
            usedWords.add(curr);
        }
        
        return new int[]{0, 0};
    }
}
  1. Set선언하고 첫 번째 단어는 사용된 걸로 넣기
  2. 현재 단어가 Set에 포함되어 있거나, 이전 단어와 현재 단어의 첫번째 글자가 다르면 탈락자
    1. 탈락자 번호
    2. 탈락자 턴 계산
  3. {플레이어번호, 턴} 매핑해서 반환​

3. 오답 / 어려웠던 점

1) usedWords.add(curr); 위치

→ 새 단어를 추가하는 부분을 탈락 검사 이후에 넣어야 함

만약 usedWords.add(curr)을 검사하기 전에 해버리면 어떤 문제가 생길까?

words = {"tank", "kick", "know", "kick"}

kick이 두 번 나오는데 usedWords.add(curr)을 먼저 했다면, kick은 이미 Set에 들어가 있으니까 검사 전에 넣어버려서 중복 여부 확인이 제대로 안 됨

2) 플레이어 번호 계산

플레이어번호는 (i % n) + 1이다.  처음에는 좀 이해가 안 됐는데 순서대로 하나씩 써 보니까 이해 됐다.
아래 패턴을 보면 i를 n으로 나눈 나머지가 0,1,2가 반복된다. 여기에 1씩 더하면 플레이어 번호가 된다.

i = 0 → 1번
i = 1 → 2번
i = 2 → 3번
i = 3 → 1번
i = 4 → 2번
i = 5 → 3번
i = 6 → 1번
...

3) 차례 계산

i   i / 3
0 → 0
1 → 0
2 → 0   (0턴째 진행 중)
3 → 1
4 → 1
5 → 1   (1턴째 진행 중)
6 → 2
7 → 2
8 → 2   (2턴째 진행 중)
...

즉, i / n은 0부터 시작한다. 그래서 +1을 한다.



Back to top