[006] 영어 끝말잇기

 

문제 설명
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 해주세요.

입출력 예
n words result
3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3]
5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0]
2 ["hello", "one", "even", "never", "now", "world", "draw"] [1,3]

입출력 예 설명
입출력 예 #1
3명의 사람이 끝말잇기에 참여하고 있습니다.

1번 사람 : tank, wheel, mother
2번 사람 : kick, land, robot
3번 사람 : know, dream, tank
와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2
5명의 사람이 끝말잇기에 참여하고 있습니다.

1번 사람 : hello, recognize, gather
2번 사람 : observe, encourage, refer
3번 사람 : effect, ensure, reference
4번 사람 : take, establish, estimate
5번 사람 : either, hang, executive
와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3
2명의 사람이 끝말잇기에 참여하고 있습니다.

1번 사람 : hello, even, now, draw
2번 사람 : one, never, world
와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

---

 

 

오답 

class Solution {
    public int[] solution(int n, String[] words) {
 int[] answer = {0, 0};

        for(int i = 0; i < words.length; i++){

        // 한사람씩 단어를 말함. n의 사람이 말을 하는 거니까 3인일 경우 0, 1, 2 - 3, 4, 5, 와 같은 수.
        // 이전 단어의 마지막 문자로 시작하는 단어를 말해야함.
        // 이전 단어의 마지막 문자로 시작하지 않는 단어를 말하면 탈락.
        // 이전에 등장했던 단어를 말해도 탈락.
        // 탈락자가 발생한 턴의 번호와, 그 사람이 몇 번째에 탈락했는지를 리턴.

            // 첫번째 순서는 비교값이 없으므로 제외 && 전 순서의 마지막 글자와 현재 글자의 첫번째 순서가 다를 경우
            if(i != 0 && words[i-1].charAt(words[i-1].length()-1) != words[i].charAt(0)) {

                // 탈락자의 번호는  n의 배수에서 나머지 순서이므로 나머지를 구하고, 인덱스는 0으로 시작하기 때문에 +1
                // 탈락자의 순서는 n으로 나눈 몫에 +1
                answer = new int[]{i% n + 1, i / n + 1};
                break;
            }else{
                // 이전에 등장했던 단어인지를 검증
                for(int j = 0; j < i; j++){
                    if(i != 0 && words[i].equals(words[j])){
                        
                        answer = new int[]{i% n + 1, i / n + 1};
                        break;
                    }
                }
            }


        }

        return answer;
    }
}

 

처음에 분명 어렵지 않게 풀리긴 했는데, 이와 같은 과정에서 계속해서 19, 20번에 문제가 생겼다

분명 식 자체는 맞는 거 같은데 무슨 문제일까 생각해보니 중복을 찾는 과정에서의 문제였다.

(정확한 원인 자체는 모르겠지만 추정으로는 그렇다)

 

오답의 풀이에서는 탈락할 경우 바로 브레이크를 시키고, 그게 아니면 넘어와서 다음 식으로 넘어가는데 저기에서 현재 가진 것과 과거를 반복문을 통해 검을을 하고, 거기에서 값을 체크하는데 아마도? 저기에서 중복값을 제대로 검수하지 못하는 모양이었다. 어떻게 하면 좋을지 고민하던 차에 hashMap을 사용하기로 한다. (해시맵은 원래 사용을 잘 안 한다.. 왜냐면 얘는 순차저장도 안 해주고.. 어쩌구...)

 

import java.util.HashSet;

class Solution {
    public int[] solution(int n, String[] words) {
int[] answer = {0, 0};
        HashSet<String> set = new HashSet<>();

        for(int i = 0; i < words.length; i++){

            // 첫번째 순서는 비교값이 없으므로 제외 && 전 순서의 마지막 글자와 현재 글자의 첫번째 순서가 다를 경우
            if(i != 0 && words[i-1].charAt(words[i-1].length()-1) != words[i].charAt(0)) {
                // 탈락자의 번호는  n의 배수에서 나머지 순서이므로 나머지를 구하고, 인덱스는 0으로 시작하기 때문에 +1
                // 탈락자의 순서는 n으로 나눈 몫에 +1
                answer[0] = i% n + 1;
                answer[1] = i/ n + 1;
                return answer;
            }else{
                set.add(words[i].toString());
                if(i != 0 && set.size() != i+1){
                     answer = new int[]{i% n + 1, i/n +1};
                    return answer;
                }
            }

        }

        return answer;
    }
}

 

이건 정답

최대한 코드를 적게 쓰려고 노력해봤다.

break는 무조건 리턴까지 가기 때문에 리턴 또한 브레이크 대신 옮겼다

 

과정은 다음과 같다

1. 우선 순서대로 단어를 가져온다

2. 첫번째 순서가 아니라면, 바로 전의 단어와 각각 제일 끝자리, 제일 앞자리를 비교한다

3. 여기에서 문제가 생긴다면 탈락자는 순서를 나눈 값 +1 (배열은 0부터 시작하므로) 이기 때문에 해당하는 것을 0에 반환한다

4. 순서의 경우는 나눈 값에서 + 1을 한다. 

5. 틀린 사람이 없다면 값을 중복 확인을 위한 set에 저장한다

6. 마찬가지로 첫번째 사람이 아니고,  현재 저장된 전체 set 길이(lengh는 언제나 1로 시작하기 때문에 i+1) 보다 작다면 그것은 중복값이라는 것이기 때문에 마찬가지로 순서를 저장한다

 

완주의 경우는 처음에 명명할 때 0, 0을 디폴트로 넣어주게 되면서 나중에 이걸 체크하게 되는 일을 방지했다.