Programmers - 영어 끝말잇기 (Java) (Lv.2)

*모든 풀이 코드는 직접 작성하였습니다.

문제

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

1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
이전에 등장했던 단어는 사용할 수 없습니다.
한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.
tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
(계속 진행)
끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

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

제한 사항

끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
단어의 길이는 2 이상 50 이하입니다.
모든 단어는 알파벳 소문자로만 이루어져 있습니다.
끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
정답은 [ 번호, 차례 ] 형태로 return 해주세요.
만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

문제 풀이

좀 어려웠다. 생각해야 될 게 많았다. 중복되는 값이 있을경우 반환, 앞뒤 글자가 끝말잇기가 안될 경우 반환, 성공하면 {0,0} 반환...

중복을 체크하는 법은 HashSet으로, 앞뒤 문자 체크는 for문으로 했다.
turnCount는 몇 바퀴 돌았는지, 즉 자기 순서가 몇번 왔는지 체크하는 변수고,
nCount는 몇 번째 사람인지 체크하는 변수다. nCount가 주어진 n보다 커지면, 즉 한 바퀴를 다 돌면 nCount를 1로 초기화 하고, turnCount에 1을 더한다.

HashSet으로 중복을 체크할때는 nCount를 1부터 시작해도 상관 없지만,
for문으로 앞뒤 체크 할때는 배열의 범위를 벗어나는 예외가 발생할 수 있기에 nCount를 2부터 시작한다.

++이 두 순회를 하나로 합쳐서도 해봤다. 이게 제일 깔끔한 정답일 듯 하다.

풀이 코드(일반)

import java.util.HashSet;

class Solution {
    public int[] solution(int n, String[] words) {
    //카운트 변수들 선언
        int turnCount = 1;
        int nCount = 2;
        int hashTurnCount = 1;
        int hashNCount = 1;
        //중복 체크를 위한 HashSet 선언
        HashSet<String> set = new HashSet<String>();
        //for-each 문으로 카운트 및 요소 체크
        for(String s : words){
            if(hashNCount > n) {
                hashNCount = 1;
                hashTurnCount++;
            }
            //HashSet에 배열 요소를 넣는걸 실패할 경우(HashSet은 중복이 허용되지 않으므로), 값 반환
            if(!set.add(s)) {
                return new int[] {hashNCount, hashTurnCount};
        }
            hashNCount++;
        }
        //앞뒤 문자 체크 for문
        for(int i = 1; i < words.length; i++){
        //차례가 한 바퀴 돌면 실행
            if(nCount > n) {
                nCount = 1;
                turnCount++;
            }
            //앞뒤 문자가 다를 경우 반환
            if(words[i].charAt(0) != words[i - 1].charAt(words[i - 1].length() - 1)){
                return new int[] {nCount, turnCount};
            }
            nCount++;
        }
        return new int[] {0, 0};
    }
}

풀이 코드(개선)

import java.util.HashSet;

class Solution {
    public int[] solution(int n, String[] words) {
        HashSet<String> set = new HashSet<String>();
        //마지막 글자 선언
        char lastEnd = words[0].charAt(0);

        for(int i = 0; i < words.length; i++){
            //첫 문자가 아님과 동시에, i번째 단어의 첫 글자가 lastEnd와 다르거나, 이미 중복일 경우
            if(i != 0 && (words[i].charAt(0) != lastEnd || set.contains(words[i]))) 
                return new int[] {i % n + 1, i / n + 1};
            //set에 i번째 문자 저장
            set.add(words[i]);
            //lastEnd 업데이트
            lastEnd = words[i].charAt(words[i].length() - 1);
        }
        return new int[] {0, 0};
    }
}