문제 설명
1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
- 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
- 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
- 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
- 이전에 등장했던 단어는 사용할 수 없습니다.
- 한 글자인 단어는 인정되지 않습니다.
다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.
tank → kick → know → wheel → land → dream → mother → robot → tank
위 끝말잇기는 다음과 같이 진행됩니다.
- 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
- 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
- 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
- 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
- (계속 진행)
끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.
사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.
접근법
해당 문제에서 설명하는 게임이 실생활에서도 많이 접해봤던 끝말잇기 게임이라 문제를 이해하는게 어렵지는 않았다
다음과 같이 간단하게 풀이 방법을 생각해 보았다.
1. 순서대로 끝말잇기 진행
2. 만약 이전 단어의 끝 문자와 이어지지 않는 단어를 말하거나 이미 말했던 단어면 탈락
3. 그렇지 않으면 계속 진행
function solution(n, words) {
// 아무도 틀리지 않고 게임이 끝날 수 있기 때문에 예외처리 [0,0]
var answer = [0,0], usedWord ={};
// 이전 단어
let preWord = words[0];
usedWord[preWord] = true;
for(let i=1; i<words.length; i++){
//현재 단어
let cWord = words[i];
// 탈락
if(preWord[preWord.length-1] != cWord[0] || usedWord[cWord] != undefined){
answer = [ Math.floor((i%n) + 1), Math.floor((i/n) +1)];
break;
}
//for문을 다시 돌기 전에 현재 단어를 이전 단어로 지정하고 사용했던 단어로도 지정한다.
preWord = cWord;
usedWord[cWord] = true;
}
return answer;
}여기서 문제는 번호와 차례를 구하는 식이였다.
번호를 구하는 식은 i 나누기 n의 나머지 +1이다
현재 i는 인덱스 번호 기준이기 때문에 원래 번호로 쓰려면 +1을 해야 한다
하지만 원래 번호대로 쓰면 문제가 생긴다.
ex) n은 3이고 틀린 word가 words에서 5번째 순서라면 5%3 -> 2가 된다 2번째 순서가 맞다 하지만 6번째 순서에서 틀린다면 6%3 -> 나머지가 0이된다. 즉 n의 배수에 해당하는 순서에서 틀리면 0이 된다.
간단하게 구하기 위해서 i는 현재 순서 -1이기 때문에 (i%3) +1을 하면 해당 번호를 구할 수 있다.
이와 마찬가지로 차례를 구하는 식은 i 나누기 n의 몫 +1이다. (i/n) +1
