[프로그래머스] 영어 끝말잇기 - Lv.2

프로그래머스 12981번 문제인 "영어 끝말잇기" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] 영어 끝말잇기 Lv.2 - [파이썬/python]

 

 

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

---

💻 문제 설명

 

부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

 

tank → kick → know → wheel → land → dream → mother → robot → tank

 

위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

 

사람의 수 n과 사람들이 순서대로 말한 단어 words가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 반환(return) 하도록 solution 함수를 완성해주세요.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12981

프로그래머스

---

🚨 제한사항

 

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 반환(return) 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 반환(return) 해주세요.

---

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

 

프로그래머스-영어-끝말잇기-파이썬-코드

 

def solution(n, words):

    words_set = set() # 사용된 단어를 저장하기 위한 set() 생성 / 중복 방지용

    words_set.add(words[0]) # 첫 번째 단어를 세트에 추가

   

    # 두 번째 단어부터 마지막 단어까지 순회

    for i in range(1, len(words)):

       

        # 만약 현재 단어가 이미 사용된 단어이거나

        # 이전 단어의 마지막 글자와 현재 단어의 첫 글자가 다르다면

        if (words[i] in words_set) or (words[i-1][-1] != words[i][0]):

           

            # 탈락자의 번호와 차례를 반환

            # 번호는 인덱스를 사람 수로 나눈 나머지에 1을 더한 값

            # 차례는 인덱스를 사람 수로 나눈 몫에 1을 더한 값

            return [(i%n)+1, (i//n)+1]

       

        # 현재 단어를 사용된 단어의 set()에 추가

        words_set.add(words[i])

       

    # 모든 단어가 규칙에 맞게 사용되었다면 [0, 0]을 반환

    return [0, 0]

 

 

---

⏱ 시간복잡도

 

위 코드의 시간 복잡도는 O(n)입니다.

 

 

단어 순회하기: for i in range(1, len(words))

주어진 단어들을 순서대로 순회하는 데 O(n)의 시간이 소요됩니다. 여기서 n은 단어의 개수입니다.

 

set() 조작하기: words_set.add(words[i]), words[i] in words_set

set()에서 원소를 추가하거나 원소의 존재 여부를 확인하는 데는 상수 시간, 즉 O(1)의 시간이 소요됩니다. 이러한 연산들은 단어의 개수에 대해 한 번씩 수행되므로, 전체적으로는 O(n)의 시간이 소요됩니다.

 

따라서, 이 코드는 단어들을 한 번만 순회하고, 각 단어에 대해 상수 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(n)입니다. 이는 입력 크기에 선형적으로 비례하는 시간 복잡도를 의미합니다.

---

🏳‍🌈 테스트 결과

 

프로그래머스-영어-끝말잇기-상태

 

프로그래머스-영어-끝말잇기-테스트-결과