문제 요약
n명의 사람이 번호 순서대로 영어 끝말잇기를 진행한다.
끝말잇기에서는 다음 규칙을 지켜야 한다.
앞 단어의 마지막 문자로 시작하는 단어를 말해야 한다.
이전에 등장한 단어를 다시 사용할 수 없다.
한 글자인 단어는 사용할 수 없다.
마지막 사람 다음에는 다시 1번 사람부터 시작한다.주어진 단어 목록에서 가장 먼저 규칙을 위반한 사람의 번호와 그 사람의 차례를 구해야 한다.
탈락자가 없다면 [0, 0]을 반환한다.
핵심 아이디어
단어를 순서대로 확인하면서 다음 두 가지를 검사한다.
현재 단어가 이전에 등장했는가
현재 단어의 첫 문자가 이전 단어의 마지막 문자와 같은가이전에 등장한 단어를 빠르게 확인하기 위해 set을 사용한다.
used_words = {words[0]}set은 특정 값이 포함되어 있는지 평균 O(1) 시간에 확인할 수 있다.
규칙을 위반한 단어의 배열 인덱스를 i라고 하면 사람 번호와 차례는 다음과 같이 계산할 수 있다.
person = i % n + 1
turn = i // n + 1파이썬 배열의 인덱스는 0부터 시작하지만 사람 번호와 차례는 1부터 시작하므로 마지막에 1을 더한다.
풀이 과정
1. 첫 번째 단어 저장
첫 번째 단어는 비교할 이전 단어가 없으므로 사용된 단어 집합에 먼저 저장한다.
used_words = {words[0]}2. 두 번째 단어부터 순회
첫 번째 단어는 이미 저장했으므로 인덱스 1부터 확인한다.
for i in range(1, len(words)):3. 중복 단어 검사
현재 단어가 used_words에 있다면 이전에 이미 등장한 단어다.
words[i] in used_words이 경우 현재 단어를 말한 사람이 탈락한다.
4. 끝말잇기 연결 검사
이전 단어의 마지막 문자와 현재 단어의 첫 문자가 같은지 확인한다.
words[i - 1][-1] != words[i][0]두 문자가 다르면 끝말잇기 규칙을 위반한 것이다.
5. 한 글자 단어 검사
현재 단어의 길이가 1이라면 규칙을 위반한 것이다.
len(words[i]) == 1제한사항에서는 모든 단어의 길이가 2 이상이라고 주어지지만, 문제의 규칙을 코드에 명확히 반영하기 위해 함께 검사할 수 있다.
6. 탈락자 번호와 차례 계산
규칙을 위반한 단어의 인덱스가 i라면 사람 번호는 다음과 같다.
person = i % n + 1해당 사람이 몇 번째 차례에 탈락했는지는 다음과 같다.
turn = i // n + 17. 정상 단어 저장
모든 규칙을 통과한 단어는 사용된 단어 집합에 추가한다.
used_words.add(words[i])8. 탈락자가 없는 경우
모든 단어를 확인할 때까지 규칙 위반이 없다면 다음 값을 반환한다.
return [0, 0]Python 코드
def solution(n, words):
used_words = {words[0]}
for i in range(1, len(words)):
current_word = words[i]
previous_word = words[i - 1]
# 중복된 단어인지 확인한다.
is_duplicate = current_word in used_words
# 앞 단어의 마지막 문자로 시작하는지 확인한다.
is_disconnected = previous_word[-1] != current_word[0]
# 한 글자인 단어인지 확인한다.
is_one_letter = len(current_word) == 1
if is_duplicate or is_disconnected or is_one_letter:
person = i % n + 1
turn = i // n + 1
return [person, turn]
used_words.add(current_word)
return [0, 0]코드 설명
사용한 단어 집합
used_words = {words[0]}이미 등장한 단어를 저장하는 집합이다.
리스트를 사용하면 중복 여부를 확인할 때 저장된 단어를 처음부터 순회해야 하지만, 집합을 사용하면 평균적으로 빠르게 확인할 수 있다.
현재 단어와 이전 단어
current_word = words[i]
previous_word = words[i - 1]변수에 현재 단어와 이전 단어를 저장하면 각 규칙 검사의 의미가 더 분명해진다.
중복 검사
is_duplicate = current_word in used_words현재 단어가 이미 사용된 단어 집합에 존재하면 중복이다.
중복 단어를 말한 사람이 즉시 탈락한다.
연결 검사
is_disconnected = previous_word[-1] != current_word[0]previous_word[-1]은 이전 단어의 마지막 문자다.
current_word[0]은 현재 단어의 첫 번째 문자다.
두 문자가 다르면 끝말잇기가 이어지지 않는다.
사람 번호 계산
person = i % n + 1사람 번호는 1부터 n까지 반복된다.
예를 들어 n = 3이라면 인덱스별 사람 번호는 다음과 같다.
인덱스: 0 1 2 3 4 5 6
사람 번호: 1 2 3 1 2 3 1인덱스를 n으로 나눈 나머지를 이용하면 반복되는 사람 번호를 계산할 수 있다.
차례 계산
turn = i // n + 1인덱스를 사람 수 n으로 나눈 몫은 몇 바퀴가 진행되었는지를 나타낸다.
예를 들어 n = 3이라면 다음과 같다.
인덱스: 0 1 2 | 3 4 5 | 6 7 8
차례: 1 1 1 | 2 2 2 | 3 3 3즉시 반환
return [person, turn]문제에서는 가장 먼저 탈락한 사람을 구해야 한다.
단어를 순서대로 확인하고 있으므로 첫 번째 규칙 위반을 발견한 순간 결과를 반환하면 된다.
예시
다음과 같은 끝말잇기를 살펴보자.
n = 3
tank -> kick -> know -> wheel -> land
-> dream -> mother -> robot -> tank마지막 tank는 첫 번째 단어로 이미 사용되었다.
마지막 tank의 배열 인덱스는 8이다.
사람 번호는 다음과 같다.
8 % 3 + 1 = 3차례는 다음과 같다.
8 // 3 + 1 = 3따라서 결과는 다음과 같다.
[3, 3]시간 복잡도
단어의 개수를 W라고 하자.
모든 단어를 한 번씩 확인하고, 집합에서의 중복 검사는 평균적으로 O(1)에 동작한다.
O(W)문자열의 해시 계산 비용까지 엄밀하게 고려하면 단어 길이의 영향을 받을 수 있지만, 이 문제에서는 각 단어의 길이가 최대 50이므로 충분히 빠르게 동작한다.
공간 복잡도
사용된 단어들을 집합에 저장한다.
O(W)최악의 경우 모든 단어가 서로 다르므로 모든 단어가 집합에 저장된다.
정리
이 문제는 단어를 순서대로 확인하면서 중복 여부와 문자 연결 여부를 검사하는 구현 문제다.
풀이 흐름은 다음과 같다.
첫 번째 단어를 집합에 저장
두 번째 단어부터 순서대로 확인
중복 단어와 연결 실패 여부 검사
규칙 위반 시 인덱스로 사람 번호와 차례 계산
모든 단어가 정상이면 [0, 0] 반환set을 이용한 중복 검사와 나머지 및 몫 연산을 이용한 순서 계산이 핵심이다.
