[Lv2.] 영어 끝말잇기

👉 사용 언어 : PYTHON3

영어 끝말잇기

✅ Solution

import math

def solution(n, words):
    ans = []
    temp = []
    for i in range(len(words)):
        if len(temp) > 0 and temp[-1][-1] != words[i][0] or words[i] in temp:
            break
        temp.append(words[i])
    if len(temp) == len(words):
        return [0,0]
    else:
        if (len(temp)+1) % n == 0:
            ans.append(n)
        else:
            ans.append((len(temp)+1) % n)
        ans.append(math.ceil((len(temp)+1) / n))
        return ans

 

👉 문제 설명 및 제한 사항

• 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기 진행중
• 규칙
  • 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다. 
  • 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다. 
  • 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다. 
  • 이전에 등장했던 단어는 사용할 수 없습니다. 
  • 한 글자인 단어는 인정되지 않습니다.
• 예시
  • tank → kick → know → wheel → land → dream → mother → robot → tank
  • 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락❗️
• 매개변수
  • 사람의 수 n
    • 2 <= n <= 10 자연수
  • 사람들이 순서대로 말한 단어 words 
    • n <= 배열 길이 <= 100
    • 2 <= 단어(원소) 길이 <= 50
    • 모든 단어는 알파벳 소문자 로만❗️
• 리턴값
  • [가장 먼저 탈락하는 사람의 번호, 그 사람이 자신의 몇 번째 차례 에 탈락하는지]
  • 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]

👉 아이디어

• temp 배열을 하나 생성한다.
• words 배열을 순회하며 현재 원소(단어)의 맨 앞 문자와 temp 배열 맨 끝 단어의 맨 끝 문자를 비교한다.
  • 비교한 문자가 같지 않거나 이미 temp 배열에 있는 단어라면 반복문을 종료한다.
  • 그렇지 않으면 temp 배열에 현재 단어를 추가하고 계속 순회해나간다.
• temp 배열의 길이에 따라 값을 리턴한다.
  • temp 배열 길이 == word 배열 길이 : 탈락자가 생기지 않으므로 [0, 0]
  • temp 배열 길이 != word 배열 길이
    • temp 배열 : 탈락자 전 순서의 단어까지만 들어있기 때문에 +1을 한 후, 계산한다.
    • 번호 : (temp 배열 길이 + 1) % n ( 이 값이 0이면 n )
    • 차례 : (temp 배열 길이 + 1) / n 올림값

 

✅ 다른 사람 풀이 참고

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]

 

👉 깨달은 것 / 알게된 것

• 시간복잡도를 고려하여 문자열 슬라이싱이 아닌 보조배열을 생성하여 pop, append 하는 방법을 택했는데 결과적으로 크게 차이가 없다.
• (len(temp)+1) % n 로 풀이하면 나머지가 0 일 경우를 또다른 조건으로 체크해줘야 하는데 +1 을 나머지 연산 후, 실행하면 따로 조건을 나눌 필요가 없어진다.
• 차례를 구할 때도 마찬가지로 +1 을 // 연산 후, 실행함으로써 내장 함수 ceil을 사용할 필요가 없어진다.
• else: return을 if문과 동일한 들여쓰기에서 사용하지 않아도 가능하다❗️