문제 설명
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 함수를 완성해주세요.
제한 사항
- 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
- words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
- 단어의 길이는 2 이상 50 이하입니다.
- 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
- 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
- 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
- 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.
입출력 예
풀이
def solution(n, words):
vocabulary = [words[0][0]]
cycle = 1
for idx, word in enumerate(words):
if (vocabulary[-1][-1] != word[0]) or (word in vocabulary):
return [(idx % n) + 1, cycle]
vocabulary.append(word)
if not (idx + 1) % n:
cycle += 1
return [0, 0]해결 과정
앞사람이 말한 단어의 마지막 문자로 시작하는 단어 확인하기
이는 vocabulary에 가장 마지막으로 저장된 단어의 가장 끝 단어를 현재 가져온 단어의 첫 글자와 비교하면 된다.
파이썬은 인덱스를 거꾸로 접근하는게 가능하므로 이를 쉽게 구현할 수 있다.
vocabulary[-1][-1]다만, vocabulary에 접근하기 때문에 앞서 배열 내 요소가 존재하는지 않으면 에러가 발생한다.
이를 방지하기 위해 words의 첫 번째로 등장하는 단어의 첫 글자를 미리 vocabulary를 생성할 때 요소로 넣어둔다. 이렇게 하면 사전에 요소가 들어있는지 검사를 할 필요가 없어진다.
단어가 이전에 등장했는지 확인하기
word in vocabulary흔히 in 키워드는 딕셔너리에 사용하는 경우가 많지만 리스트에도 사용할 수 있으며, 이는 해당 값이 배열 내 요소로 들어있는지 여부를 반환한다.
현재 몇 번째 주기인지 기록하기
n명의 사람이 끝말잇기를 하므로 n번 사람이 말한 단어의 인덱스는 n - 1의 배수다.
이는 반대로 인덱스 + 1의 값이 n으로 나누어진다면 해당 사람이 n번 사람이라는 뜻이므로 해당 사람이 말한 경우 cycle의 값을 1 증가시켜 몇 번째 주기인지 기록할 수 있다.
다른 사람의 풀이
def solution(n, words):
for p in range(1, len(words)):
if words[p][0] != words[p-1][-1] or words[p] in words[:p]: return [(p%n)+1, (p//n)+1]
else:
return [0,0]우선 첫 번째로 말하는 단어는 규칙 검사가 필요 없으므로 두 번째 단어부터 검사해도 문제가 없다.
또한 이미 words라는 배열에 단어들이 기록되어 있으므로 굳이 새로 배열을 만들어 추가할 필요가 없다(불필요한 동작).
또한 주기를 따로 기록하지 않고 현재 인덱스를 n으로 나누었을 때 그 몫에 1을 더한 값이 현재 주기임을 알 수 있다.
