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

[문제 설명]

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

코딩테스트 연습 - 영어 끝말잇기

 

[풀이 과정]

풀이시간 : 22:35 ~ 23:35 (딱 한시간) (길다 길어...줄여라 시간..)

 

끝말잇기에서 탈락하는 경우는 3가지다. 

1. 한 글자인 단어를 말하는 경우

2. 첫 문자가 이전 단어의 마지막 문자가 아닌 경우 (끝말잇기 규칙을 위반)

3. 이전에 나온 단어를 또 말하는 경우(중복)

 

단어 리스트 for loop문을 돌면서 위 3가지 경우중 한가지라도 위반하는 경우에 단어리스트의 index를 반환한다.

단, index는 0부터 시작하지만 문제에서 순서는 1번부터 센다. 그러므로 index+1 을 반환해야한다. 

 

1번 경우는 설명 생략. 

 

2. 첫 문자가 이전 단어의 마지막 문자가 아닌 경우 (끝말잇기 규칙을 위반)

- String 클래스의 startWith 메소드와 substring 메소드를 사용했다. 

 if (!curW.startsWith(words[i - 1].substring(words[i - 1].length() - 1))) {
                    index = i + 1;
                    break;
                }

 

3. 이전에 나온 단어를 또 말하는 경우(중복)

- HashMap 을 사용했다. 처음 나온 단어는 Map에 <문자열, 1> 의 형태로 put한다. 

HashMap.containsKey(Object Key) 메소드를 사용하여 이미 존재하는 키인지 여부를 확인한다.

true이면 이전에 나왔던 단어였기 때문에 이미 HashMap에 put된 단어이므로 index+1을 반환하고 for문을 나온다.

 if (map.containsKey(curW)) {
     index = i + 1;
     break;
} else {
     map.put(curW, 1);
}

 

반환해야하는 값은 {가장 먼저 탈락하는 사람의 번호, 탈락한 게임의 차례 번호} 이다. 

예를 들어 1번째 사람이 3번째 돌아오는 차례에 탈락했다면 답은 {1, 3} 이다. 

여기서 조금 헷갈렸는데, 순서대로 써보면서 규칙을 찾아냈다. 

 

가장 먼저 탈락한 사람의 번호 = index%n ==0 ? n : index%n

탈락한 게임의 차례 번호 = index%n==0 ? index/n : index/n+1 

 

[JAVA code]

전체 코드다.

package com.algorithm.level2;

import java.util.Arrays;
import java.util.HashMap;

public class Test31 {
    public static void main(String[] args) {

        int n = 3;
        String[] words = {"tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"};
             /*   {"hello", "observe", "effect", "take", "either", "recognize",
                        "encourage", "ensure", "establish", "hang", "gather",
                        "refer", "reference", "estimate", "executive"};*/

        //   {"hello", "one", "even", "never", "now", "world", "draw"};

        System.out.println("answer : " + Arrays.toString(solution(n, words)));

    }

    public static int[] solution(int n, String[] words) {
        int[] answer = new int[2];
        int index = 0;
        HashMap<String, Integer> map = new HashMap<>();

        // 가장 첫번째 단어
        String curW = words[0];

        // 첫번째 단어의 길이가 1인 경우 
        if (curW.length() == 1) {
            index = 1;
        } else {
            // 첫번째 단어부터 map에 put
            map.put(curW, 1);

            // 두번째 단어부터 for loop
            for (int i = 1; i < words.length; i++) {
                curW = words[i];

                // 1. 단어의 길이가 1인 경우
                if (curW.length() == 1) {
                    index = i + 1;
                    break;
                }


                // 2. 단어의 첫번째 문자가 이전 단어의 마지막 문자가 아닌 경우
                if (!curW.startsWith(words[i - 1].substring(words[i - 1].length() - 1))) {
                    index = i + 1;
                    break;
                }

                // 3. 이전에 나왔던 단어를 또 말한 경우
                if (map.containsKey(curW)) {
                    index = i + 1;
                    break;
                } else {
                    map.put(curW, 1);
                }
            }
        }

        // 만약 index가 0이면 틀린 사람이 아무도 없는 것이므로 {0,0} 리턴
        if (index == 0) {
            return new int[]{0, 0};
        }

        answer[0] = index % n == 0 ? n : index % n;
        answer[1] = index % n == 0 ? index / n : (index / n) + 1;

        return answer;
    }
}