[프로그래머스 *Java] 영어 끝말잇기

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

프로그래머스

 

조건

제한시간 : 30분 이내

 

로직을 구현할 때, 고려해야 할 부분을 숫자를 매겨 정리하면 4가지로 정리할 수 있다.
1. 단어가 중복될 때 어떻게 처리해야할까?
2. 끝말잇기가 아닌, 다른 단어를 말할 경우?
3. 틀린 사람이 몇 번째 차례 때 틀린 것인지?
4. 틀린 사람이 누구인지?

위 네 가지만 고려하면 쉽게 문제를 풀 수 있다.
아래 코드를 보면, HashSet 보면 단어를 담아주기 위한 자료구조를 HashSet 을 사용했다.
하지만, 꼭 HashSet 을 사용할 필요가 없다.
그런데 왜 HashSet 을 사용했냐면, 시간복잡도를 고려해서 사용했다고 이야기할 수 있겠다.
단어를 저장하고, 단어가 있는지 없는지 확인을 해야하는 데, 그 때 내장함수인 contains() 라는 메서드를 사용해야 한다.
Java API 에서 여러 컬렉션에 contains() 를 메서드가 존재하는 건 알 것이다.
HashSet이 add, contains 메서드가 O(1) 시간 복잡도를 갖고 있어 그것으로 선택했다.

이제 아래 코드와 코드 주석을 보고 확인해보자.

 

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2];
        HashSet<String> wordList = new HashSet<>();
        
        // 1. 첫 번째 단어는 넣고 시작 초기화작업.
        String previousWord = words[0];
        wordList.add(words[0]);
        
        // 2. 루프를 돌면서 계속 확인, 비교
        for (int i = 1; i < words.length; i++) {
            // 2-1. 이전 단어의 끝자리와 현재 단어 앞자리가 다른지 확인.
            boolean check = previousWord.charAt(previousWord.length()-1) != words[i].charAt(0);
            
            // 2-2. check 변수 또는, 단어들이 담긴 자료구조에서 해당 단어가 있는 지 여부 체크
            if(check || wordList.contains(words[i])) {
            	// 2-3. 끝말잇기가 더 이상 안되고, 틀릴 경우 in
                answer[0] = i % n + 1; // 나머지 값을 이용해서, 사람들 중 누가 하다가 틀렸는 지 확인.
                answer[1] = i / n + 1; // 몇 번째 차례였을 때를 확인
                break;
            }
            
            wordList.add(words[i]); // 3. 위 if 조건에 해당 안될 시, 단어리스트 자료구조에 단어를 넣기
            previousWord = words[i];  // 4. 이전 값 최신화
        }
        
        return answer;
    }
}