Programmers 12981 - 영어 끝말잇기

코딩테스트 연습 - 영어 끝말잇기 | 프로그래머스 스쿨 (programmers.co.kr)

 

문제 조건

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어.
4. 이미 등장한 단어는 사용 불가
5. 한 글자는 안된다
6. 탈락자가 생기지 않는다면 [0, 0]을 반환한다.

이때 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는가.

문제의 흐름대로 구현

문제 조건을 읽으며 정리한 단서들을 조합해 보자.

우선은 앞에서부터 순회하며 읽는다.

또한 순환하고 있기 때문에 % 연산을 사용한다.

문자의 비교를 위해 charAt을 사용해서 비교를 한다.

이미 등장했던 단어를 빠르게 검색하기 위해 Hash 기반의 Set을 사용하면 될 것 같다.

예외로 한 글자 조건이 있다.

자신의 턴을 관리해줘야 한다. 이는 Map을 통해 자신의 번호 : 턴으로 관리를 하면 빠르게 찾고 수정할 수 있다.

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        Map<Integer, Integer> turn = new HashMap<>();
        Set<String> wordSet = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            turn.put(i, 1);
        }
        
        // 첫 턴 예외
        turn.put(1, 2);
        wordSet.add(words[0]);
        int id = 1;
        boolean isEnd = true;
        
        for (int i = 1; i < words.length; i++) {
            id = i % n + 1;
            String prevWord = words[i - 1];
            String word = words[i];
            
            // 탈락 조건
            if (word.length() == 1 ||
                wordSet.contains(word) ||
                prevWord.charAt(prevWord.length() - 1) != word.charAt(0)) {
                isEnd = false;
                break;
            }
        
            turn.put(id, turn.get(id) + 1);
            wordSet.add(word);
        }
        
        if (isEnd) return new int[]{0, 0};
        
        int[] answer = {id, turn.get(id)};
        
        return answer;
    }
}

코드 개선

문제의 흐름을 따라서 구현하다 보면 O(N)의 시간복잡도로 풀이가 가능하다.

이 풀이에서 따져보자면 turn을 관리하고 있는 Map 같은 경우에는 굳이 필요하지 않다.

그리고 첫 턴을 처리하는 것이 코드의 명확성을 떨어뜨린다고 생각한다.

n을 통해서 현재 턴을 (i/n + 1)로 처리하면 공간복잡도를 개선할 수 있을 것 같다.

또한 리턴을 break 시점에 하는 것이 더 빠른 명확한 처리가 될 것 같다.

문제 조건에서 1글자 단어는 인정되지 않는다고 했는데 제한 사항을 보면 단어의 길이가 2 이상 50 이하라는 제한이 있다. 따라서 1글자 검증 과정을 불필요하다.

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++) {
            if (usedWords.contains(words[i]) ||
                words[i].charAt(0) != words[i-1].charAt(words[i - 1].length() - 1)) {
                return new int[]{(i % n) + 1, (i / n) + 1};
            }
            usedWords.add(words[i]);
        }
        
        return new int[]{0, 0};
    }
}

개선사항을 통해 훨씬 읽기 좋은 코드가 됐다고 생각한다.