[Programmers][Python] 영어 끝말잇기

1. 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12981

프로그래머스

 

2. 처음 작성한 코드

• 첫 문자에 대한 변수 설정을 해준다. 첫 번째 사람은 탈락하지 않기 때문에 괜찮다.
  • words_lst 리스트는 지금까지 불린 단어를 저장하게 된다.
  • last_spell 변수는 직전 단어의 마지막 스펠을 저장하게 된다.
• enumerate를 이용하여 words 리스트에서 두 번째 문자부터 가져와 조건을 체크한다.
  • 가져온 글자의 첫 스펠과 앞 글자의 마지막 스펠이 일치하고, 글자가 이전에 말했던 글자 리스트에 존재하지 않는 조건을 체크한다.
    • 조건문과 일치하면 탈락하지 않았으므로, 가져온 글자의 스펠 마지막을 last_spell 변수에 저장하고, 글자를 words_lst 리스트에 추가한다.
    • 조건문과 일치하지 않으면 탈락자이므로, 탈락자의 순번과 몇 바퀴 째인지를 계산하여 반환한다.
• 마지막 단어를 체크할 때까지 조건에 부합할 경우 탈락자가 없으므로 [0, 0]을 반환해 준다.

      

      

      

    
    

      <python />
    
def solution(n, words):
    # 첫 문자에 대한 변수 설정
    words_lst = [words[0]]
    last_spell = words[0][-1]

    # 루프문을 통한 끝말잇기 조건 체크
    for nn, w in enumerate(words[1:]):
        # 전 글자의 끝과 앞 글자의 처음이 일치하고 글자가 중복되지 않을 때
        if w[0] == last_spell and w not in words_lst:
            last_spell = w[-1]
            words_lst.append(w)
        # 탈락자의 경우
        else:
            return [(nn + 1) % n + 1, (nn + 1) // n + 1]

    # 마지막 단어까지 탈락자가 없을 경우
    return [0, 0]

# 입출력 예시
print(solution(3, ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]))
print(solution(5, ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang",
          "gather", "refer", "reference", "estimate", "executive"]))
print(solution(2, ["hello", "one", "even", "never", "now", "world", "draw"]))

여기서 enumerate와 앞글자를 체크하는 방식 때문에 초기값을 먼저 설정하고 시작했는데, [코드1]과 같이 작성하면 비슷하지만 조금 더 간단히 작성 할 수 있다. 물론 [코드2]가 더 좋은 방법이다.
 

3. 다른 코드

[코드1]

• 변수의 사용 없이 words 리스트에서 단어 두 개를 가져와 비교하고 단어가 지금까지의 리스트에서 존재하는지 찾는 코드이다.

      

      

      

    
    

      <python />
    
def solution(n, words):
    # 루프문을 통한 끝말잇기 조건 체크
    for i in range(1, len(words)):
        # 탈락자의 경우
        if words[i-1][-1] != words[i][0] or words[i] in words[:i]:
            return [(i + 1) % n + 1, (i + 1) // n + 1]
    # 마지막 단어까지 탈락자가 없을 경우
    return [0, 0]

처음 작성한 코드와 [코드1]에서 문제가 있다면,  'in'을 사용하기 때문에 시간 복잡도가 높아지는 문제가 발생한다.
 

[코드2]

• [코드1]과 비슷하지만 지금까지 나온 단어를 저장하여 집합에 저장하고 서치 할 때 이용한다.

      

      

      

    
    

      <python />
    
def solution(n, words):
    words_set = set()
    # 루프문을 통한 끝말잇기 조건 체크
    for i in range(1, len(words)):
        # 탈락자의 경우
        if words[i-1][-1] != words[i][0] or words[i] in words_set:
            return [(i + 1) % n + 1, (i + 1) // n + 1]
        # 집합에 단어 추가
        words_set.add(words[i-1])
    # 마지막 단어까지 탈락자가 없을 경우
    return [0, 0]

집합 set은 'in'을 사용할 때 시간복잡도가 리스트대비 O(n)에서 O(1)로 줄어드므로, 반복문 이용 시 집합을 통한 'in'을 사용하는 것이 올바르다.
 
여담으로 탈락자의 순번과 몇 번째인지 루프를 계산하는 부분은 이러한 단순한 문제에서는 복잡한 연산을 해도 괜찮지만, 코드의 효율성과 확장성을 위해서는 따로 변수를 만들어서 현재 과정을 저장하는 것이 맞다고 한다.