[프로그래머스] Lv2 영어 끝말잇기 / JAVA

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

프로그래머스

---

코드

주석은 대략적인 풀이과정으로 보면된다.

class Solution {
    public int[] solution(int n, String[] words) {
        /*
        규칙성을 고민해보았으나 그냥 구현문제인 것 같다.
        $주어진 words 의 개수가 n으로 나누어떨어지지 않으면 언젠가 같은 단어를 말하게 되므로
        반드시 탈락자가 발생한다.
        */
        /*
        words 에서 인덱스%n 의 값으로 사람을 구분한다.
        각 n명이 차례를 가진 횟수를 저장하는 n 크기의 int형 배열 arr 를 기본값 0으로 만들어둔다.
        첫 사람의 첫번째는 엣지케이스로 arr[0]=1으로 저장해둔다.
        words 의 두번째 인덱스부터 순회한다. 
            먼저 arr[인덱스%n]+=1 를 한다.
            바로 앞 단어와 끝말이 이어지는 지 확인한다.
                안 이어지면 answer = [인덱스%n+1, arr[인덱스%n]], 반복문 종료
                이어지면 continue
            wrods 의 처음부터 현재 인덱스까지 중복되는 단어가 있는 지 확인한다.
                있으면 answer = [인덱스%n+1, arr[인덱스%n]], 반복문 종료
                없으면 continue
        answer 리턴
        */
        int[] result = new int[2];
        int[] arr = new int[n];
        arr[0] = 1;

        for(int i=1; i<words.length; i++){
            
            arr[i%n]+=1;
            
            if(words[i-1].charAt(words[i-1].length()-1) 
               != words[i].charAt(0)){
                result[0] = i%n+1;
                result[1] = arr[i%n];
                return result;
            }

            for(int j=0; j<i; j++){
                if(words[j].equals(words[i])){
                    result[0] = i%n+1;
                    result[1] = arr[i%n];
                    return result;
                }
            }
            
        }
        
        if(words.length%n!=0){
            result[0] = words.length%n;
            result[1] = arr[result[0]-1];
        }


        return result;
    }
}



최소한의 공간을 사용하는데 신경을 쓴 문제였다.

문제의 내용대로 각 참가자별로 배열을 두는 등의 단순한 방법이 떠올랐으나,

주어진 배열을 그대로 사용하는 방법이 떠올라 풀게 되었다.

 

먼저 n명의 참가자의 차례개수를 저장하는 int arr[] 을 선언한다. 이 배열의 인덱스가 참가자 각각을 나타낸다.

첫번째 단어를 처리하기 위해 arr[0] 에 1을 저장한다.

두번째 단어부터 words[] 를 순회하며, 1) 끝말이 이어지는 지 확인한 후  2) 중복되는 단어가 있었는 지 확인한다.

끝말이 이어지지 않는 순간과 중복되는 단어가 발견되는 순간 해당 참가자와 참가자의 차례 개수를 리턴한다.

위 과정에서 함수가 종료되지 않으면 마지막 단어를 말한 사람의 다음 사람이 결과에 담기도록 한다.

 

시간이 1시간 50분 정도 소요되었는데, 아주 단순한 이유로 시간을 많이 잡아먹었다.

String 을 == 로 비교했던 것이다... equals() 메소드를 사용하니까 바로 해결이 되었다.