[12981] 영어 끝말잇기

✔ 영어 끝말잇기

[프로그래머스 12981]

문제 분석하기

앞의 단어의 끝말로 이어지지 않거나 이미 사용한 단어 집합 안에 존재하는 단어를 말할 경우 탈락하도록 함

탈락한 사람의 번호와 탈락한 차례를 함께 반환

만약 끝까지 탈락이 발생하지 않으면 0, 0을 반환

손으로 풀어보기

1. 단어를 하나씩 확인하며 끝말로 이어지지 않을 경우 탈락, 이어질 경우 집합에 없는지 확인하고 있다면 탈락
   탈락이 아니라면 집합에 단어를 저장
2. 탈락한 사람이 있다면 탈락한 사람의 번호와 탈락한 차례를 함께 반환
   • 탈락한 사람의 번호 = 탈락한 위치(i) % n + 1
   • 탈락한 차례 = 탈락한 위치(i) / n + 1
3. 탈락한 사람이 없다면 0, 0을 반환

슈도코드 작성하기

n(사람의 수)
words(사람들이 순서대로 말한 단어)
answer(가장 먼저 탈락하는 사람의 번호와 탈락한 차례)
set(단어 집합)
for(i -> words의 길이만큼) {
    if(set이 비어있다면) {
        set에 words[i] 저장
    }
    else {
        front(앞의 단어)
        if(set에 words[i]가 포함되어 있지 않으면서 front의 끝 알파벳과 words[i]의 첫 알파벳이 같다면) {
            set에 words[i] 저장
        }
        else { 
            탈락이므로 answer[0]에 탈락한 사람의 번호, answer[1]에 탈락한 차례 저장
            break;
        }
    }
}
answer 반환

코드 구현하기

/**
 * 12981) 영어_끝말잇기
 */
public class L026_12981 {
    // n(사람의 수)
    // words(사람들이 순서대로 말한 단어)
    public int[] solution(int n, String[] words) {
        // answer(가장 먼저 탈락하는 사람의 번호와 탈락한 차례)
        int[] answer = new int[2];
        // set(단어 집합)
        Set<String> set = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            // set이 비어있다면
            if (set.isEmpty()) {
                // set에 words[i] 저장
                set.add(words[i]);
            } else {
                // front(앞의 단어)
                String front = words[i - 1];
                // set에 words[i]가 포함되어 있지 않으면서 front의 끝 알파벳과 words[i]의 첫 알파벳이 같다면
                if (!set.contains(words[i]) && front.charAt(front.length() - 1) == words[i].charAt(0)) {
                    // set에 words[i] 저장
                    set.add(words[i]);
                }
                // 이전에 등장했던 단어를 사용했거나, 끝말잇기가 이어지지 않을 경우
                else {
                    // 탈락이므로 answer[0]에 탈락한 사람의 번호, answer[1]에 탈락한 차례 저장
                    answer[0] = i % n + 1;
                    answer[1] = i / n + 1;
                    break;
                }
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L026_12981 solution = new L026_12981();

        int n = 3;
        String[] words = { "tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank" };

        int[] result = solution.solution(n, words);

        System.out.println(Arrays.toString(result));
    }
}