[알고리즘]프로그래머스 12981번 - 영어 끝말잇기

프로그래머스 12981번 - 영어 끝말잇기

프로그래머스 12981번 - https://programmers.co.kr/learn/courses/30/lessons/12981

 

요구사항

1. 영어 끝말잇기에서 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 배열에 담아 반환하라.

2. 사람의 번호는 1번부터 시작합니다.

 

요구사항 분석 및  풀이과정

1. 정상적으로 끝말이 이어지는 지를 확인하기 위하여 이전 사람이 말한 영단어의 끝 문자를 기록합니다.

 

2-1. i번째 사람이 영단어를 말했을 경우 i-1번째 사람이 말한 영단어의 끝 문자와 내가 말한 영단어의 첫 문자가 같은지를 확인합니다.

2-2. 만약 다르다면 탈락이며, 가장 먼저 탈락하는 사람의 번호(i % n + 1), 자신의 몇  번째 차례(i / n + 1)를 배열에 담아 반환합니다.

2-3. 그렇지 않은 경우는 정상적인 끝말잇기이므로 다음 차례로 넘어갑니다.

 

3-1. 2번이 성립한다면, i번째 사람이 영단어를 말했을 경우, 해당 영단어가 이전 사람들이 말한 영단어가 아닌지를 확인합니다.

3-2. 이전 사람들이 말한 영단어인지를 확인하기 위하여 매번 영단어를 말할 때 영단어를 Set 자료구조를 이용하여 기록합니다.

3-3.  만약 이전 사람들이 말한 영단어일 경우 2-2에 해당합니다. 그렇지 않은 경우는 정상적인 끝말잇기이므로 다음 차례로 넘어갑니다.

 

소스코드 작성

class Solution {

	public int[] solution(int n, String[] words) {
		Set<String> s = new HashSet<>();

		char prevLastChar = words[0].charAt(words[0].length() - 1);
        	s.add(words[0]);
        
		for (int i = 1; i < words.length; i++) {
			String word = words[i];
			char firstChar = word.charAt(0);

			if (prevLastChar == firstChar && !s.contains(word)) {
                		prevLastChar = word.charAt(word.length() - 1);
				s.add(word);
			} else {
				return new int[] {(i % n) + 1, (i / n) + 1};
			}
		}

		return new int[] {0, 0};
	}
}

 

결과

 

소스코드 깃허브 주소

링크