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

Lv.2 - 영어 끝말잇기

문제 바로가기

1. 문제 요구사항

• 입력: 사람 수 n과 순서대로 말한 단어 배열 words.
• 탈락 조건:
  1. 이전 단어의 마지막 글자와 현재 단어의 첫 글자가 다를 때.
  2. 이전에 등장했던 단어를 다시 말했을 때.
• 출력: 탈락한 사람의 번호와 몇 번째 차례에서 탈락했는지 [번호, 차례] 형태로 반환. (탈락자가 없으면 [0, 0])

2. 접근 방식 (Algorithm)

문제를 풀기 위해 검사해야 할 것은 '끝말 규칙'과 '중복 여부' 두 가지다.

1) 끝말 규칙 검사

• 현재 단어 words[i]의 첫 글자와 이전 단어 words[i-1]의 마지막 글자를 비교한다.
• String.charAt()을 사용하면 간단히 비교 가능하다.

2) 중복 검사 (HashSet 활용)

• 처음에는 ArrayList나 배열을 순회하며 중복을 찾으려 했으나, 이는 매번 리스트 전체를 뒤져야 하므로 비효율적이다.
• 검색 속도가 $O(1)$인 HashSet을 사용하여, 현재 단어가 이미 등장했는지(contains) 확인하고, 없다면 집어넣는(add) 방식을 선택했다.

3) 번호와 차례 계산

• 별도의 변수로 복잡하게 계산할 필요 없이 인덱스 i를 활용한다.
  • 번호: (i % n) + 1 (나머지 연산)
  • 차례: 변수 cnt를 두어 i가 n의 배수가 될 때마다 1씩 증가시킨다. (또는 i / n + 1 수식 활용 가능)

3. 코드

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer;
        Set<String> set = new HashSet<>();
        set.add(words[0]);
        int cnt = 1;
        
        for(int i=1; i<words.length; i++) {
            if(i % n == 0) cnt++;
            
            if(words[i].charAt(0) != words[i-1].charAt(words[i-1].length() - 1)) {
                return new int[]{i%n+1, cnt};
            }
            
            if(set.contains(words[i])) {

                return new int[]{i%n+1, cnt};
            }
            set.add(words[i]);
            
        }
        
        return new int[]{0, 0};
    }
}

4. 느낀점 & 배운점

1. 자료구조 선택의 중요성 (HashSet)
   단순 구현으로도 풀 수 있지만, "중복 체크"라는 키워드를 보자마자 Set을 떠올릴 수 있어야 한다. 리스트 탐색은 $O(N)$이지만 해시 탐색은 $O(1)$이기 때문에 데이터가 커질수록 성능 차이가 극명해진다.

2. 순서의 중요성
   Set에 데이터를 넣는 시점이 중요했다. 무작정 add부터 하면 contains 검사 시 자기 자신이 감지되어버린다. 반드시 검사(contains) → 등록(add) 순서를 지켜야 논리적 오류가 발생하지 않는다.

3. 디버깅
   처음에는 반복문 안에서 set.add(words[0])라고 잘못 적는 실수를 했다. 코드를 짤 때 변수명을 정확히 사용했는지, 루프 안에서 올바른 인덱스를 참조하고 있는지 꼼꼼히 확인하는 습관을 들여야겠다.