[201125] 영어 끝말잇기 - Summer/Winter Coding(~2018) (level2)

0. 문제 유형 : 규칙찾기, 적절한 자료구조(중복 처리)
1. 문제 이해

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

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

(1) 주요 요구사항

규칙에 맞게 끝말잇기를 진행하여 [탈락하는 사람의 번호, 자신의 몇 번째] 를 출력

[규칙]
1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다. → 문자 비교 필요
4. 이전에 등장했던 단어는 사용할 수 없습니다. → 중복 확인 필요
5. 한 글자인 단어는 인정되지 않습니다.

 

(2) 제한 사항

- n : 끝말잇기에 참여하는 사람 수 - 2이상 10이하의 자연수

- words : 끝말잇기에 사용한 단어들 - n이상 100이하의 길이

- 각 단어 길이 : 2이상 50이하

- 모든 단어는 소문자로만 이루어짐

- 탈락자가 없는 경우 : [0, 0] 출력

 

 

2. 전략

(1) 문자 비교 : 문자열의 인덱스와 charAt 이용

- 앞의 문자의 마지막 문자 : words[i-1].charAt(words[i-1].length() - 1)

- 현재 문자의 첫 문자 : words[i].charAt(words[i])

→ 둘을 비교하여 다르면 (3)으로

 

(2) 중복 확인 : HashSet<String>

- 한 문자를 만날때마다 HashSet에 add

- add결과 false이면 중복이 있으니 (3)으로

 

(3) [탈락하는 사람의 번호(index), 자신의 몇 번째(order)] 구하는 방법

- index = i % n + 1

(n 단위로 나눈 후의 나머지를 보면 알 수 있음)

- order = i / n + 1

(n 단위로 몇 번 나눠지는 지 몫을 보면 알 수 있음)

 

 

3. 참고 사항

 

 

4. 코드

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        int index = 0; int order = 0;
        HashSet<String> hash = new HashSet<>();
        hash.add(words[0]);
        for(int i = 1; i < words.length; i++){
            if(words[i-1].charAt(words[i-1].length()-1) != words[i].charAt(0) || !hash.add(words[i])){
                index = i % n + 1;
                order = i / n + 1;
                break;
            }
        }
        int[] answer = new int[]{index, order};
        return answer;
    }
}