[Programmers] L2. 영어 끝말잇기 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

💡 탈락 조건 : 같은 단어인 경우, 끝말잇기가 성립이 안 되는 경우

 

게임 진행 정보 초기화

• 몇 번째 게임(라운드)인지 저장할 변수와, 현재 차례를 저장할 변수를 생성한다.
  
  • 두 번째 단어부터 순회하므로 모두 1로 설정한다.
• 현재 단어의 첫 글자와 비교하기 위해, 직전 단어의 마지막 글자를 저장하기 위한 변수를 생성한다.
  • 첫 번째 단어의 마지막 단어를 저장한다.
• 중복 여부를 확인하기 위해 사용된 단어를 저장할 리스트를 생성한다. (set 를 사용하는 것이 효율적이다.) 
  • 맨 처음 인덱스에 첫 번째 단어를 저장한다.

단어 리스트 순회

• 차례가 사람 수와 같아지면 게임 횟수를 증가시키고, 차례를 1로 다시 초기화한다. 그게 아니면 차례를 증가시킨다.
• 각 단어를 확인하며, 현재 단어가 끝말잇기 규칙에 맞는지와 중복 단어인지를 확인한다.
  • 첫 번째 글자와 이전에 저장한 마지막 글자가 일치하지 않으면 끝말잇기가 성립되지 않는다.
  • 사용한 단어를 담은 리스트에 현재 단어가 있다면 중복된 단어가 있다는 것이다.
• 규칙을 위반했거나 중복 단어가 나오면 탈락자의 번호와 라운드를 반환한다.
• 문제가 없으면 현재 단어의 마지막 글자를 저장하고, 현재 단어를 사용된 단어를 저장하는 리스트에 추가한다.

탈락자가 없는 경우

• 모든 단어를 문제없이 끝말잇기 규칙에 맞게 말한 경우 [0, 0]을 반환한다.

 

Solution

def solution(n, words):
    game, cnt = 1, 1  # 게임 횟수, 차례
    end = words[0][-1]  # 첫 번째 단어 끝 저장
    used = [words[0]]  # 사용한 단어 저장
    for i in words[1:]:
        if cnt >= n:
            game += 1
            cnt = 1
        else:
            cnt += 1

        if i[0] != end or i in used:  # 끝말잇기 성립 확인/같은 단어 체크
            return [cnt, game]
            
        end = i[-1]  # 마지막 글자 저장
        used.append(i)
        
    return [0, 0]

 

 

개선할 점

• 단어 중복 확인 시 used 리스트에 매번 in 연산을 사용하여 검색하는 부분을 개선할 수 있다. 리스트에서의 in 연산은 O(n)의 시간이 소요되므로, 단어가 많을수록 시간이 증가한다.
• set 자료구조를 사용하면, 단어 중복 확인이 O(1)의 시간으로 효율적으로 처리될 수 있다. used 리스트 대신 used 집합을 활용하여 중복 검사를 빠르게 수행하는 방식으로 개선할 수 있다.

 

개선된 코드

def solution(n, words):
   	...
    used = {words[0]}  # 사용한 단어를 저장할 집합으로 초기화

    for i in words[1:]:
        ...
        used.add(i)  # 집합에 단어 추가
        
    return [0, 0]

---

👩‍💻 회고

중복 단어를 체크하는 코드에서 문제가 많았다. 처음에는 기존 리스트에서 중복된 단어가 있는지 체크했더니 올바른 결과가 나오지 않았다.

if i in words[:words.index(i)]:

 

위 코드처럼 작성하면, words.index(i)는 해당 단어가 리스트에서 처음 나타난 위치를 반환하기 때문에, 중복 단어가 있을 경우 첫 번째 위치에서 잘못된 결과가 발생할 수 있다. 따라서 사용된 단어를 따로 저장하고 확인해야 한다.

---