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

1. 문제

---

프로그래머스

2. 풀이 과정

---

끝맛일기에서 탈락자가 나오는 경우는 두 가지이다.

 

1. 이전 단어의 마지막 글자로 시작하지 않은 경우

2. 이미 나온 단어를 다시 말한 경우

 

이 두 가지 조건에 해당하면 그 순간의 유저 번호와 몇번째 사이클이었는지를 반환하면 된다.

1. 이전 단어의 마지막 글자로 시작하지 않은 경우를 체크하기 위해 HashSet을 사용하고

2. 이미 나온 단어를 다시 말한 경우를 체크하기 위해 이전 단어의 마지막 단어와 현재 단어의 첫번째 단어를 비교했다.

 

이게 끝이다. 이제 코드를 보자

 

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(int n, String[] words) {
        
        int[] answer = new int[2];
        
        HashSet<String> wordSet = new HashSet<>(); // 중복 단어 체크
        String beforeWord = "___"; // 이전 사람이 말한 단어
        
        for(int i = 0; i < words.length; i++) {
            
            String word = words[i];
            int turn = i % n + 1; // 현재 몇번째 사람의 턴인지
            int cycle = i / n + 1; // 현재 몇번째 사이클인지
            
            // 1. 이전 단어의 마지막 글자로 시작하지 않는 경우
            String lastChar = 
                beforeWord.substring(beforeWord.length() - 1);
            String firstChar =
                word.substring(0, 1);
            
            if(i != 0 && !lastChar.equals(firstChar)) { // 첫번째는 무조건 통과
                answer[0] = turn;
                answer[1] = cycle;
                break;
            }
            
            // 2. 이미 나온 단어를 다시 말한 경우
            if(wordSet.contains(word)) {
                answer[0] = turn;
                answer[1] = cycle;
                break;
            }
            
            // 3. 정상적인 단어라면 그 단어를 wordSet에 추가
            wordSet.add(word);
            
            // 4. 현재 단어 이전 단어로 만들기
            beforeWord = word;
        }
        
        return answer;
        
        
    }
}

시간 복잡도

• O(N)

 

4. 피드백

---

• 중복체크 할 때는 HashSet