[프로그래머스] Lv2. 영어 끝말잇기

문제

풀이

1. 언급된 단어들을 저장할 자료구조 필요

일반 배열로 저장하면 in으로 찾아야하는데 시간복잡도가 O(n)이기 때문에 이 방법은 비효율적일 거 같았다. 대신 단어를 키 값으로 저장할 수 있는 딕셔너리를 사용하면 현재 단어가 있는지 확인하는데 시간복잡도가 O(1)이라 더 효율적이라 생각했다

2. 얼마나 진행됐는가 확인

cnt로 현재까지 얼마나 진행됐는지 횟수를 계산하고 사람의 머릿수(n)로 나눠주게 되면 몫이 현재까지 진행된 차례고, 나머지가 번호가 된다. 카운트는 0부터 시작하기 때문에 +1을 해주면 정확한 값이 된다

3. 이전 사람이 말한 마지막 단어 확인

문자열 변수 last를 통해 단어를 말할 때마다 이 값을 업데이트 시켜주었다. 굳이 직전의 모든 단어를 다 저장할 필요가 없기 때문에 딱 마지막 단어 한 글자만 저장했다.

def solution(n, words):
    
    # 언급된 단어들을 저장해둘 딕셔너리
    dic = {words[0]: True}
    
    # cnt: 얼마나 진행됐는가 확인할 변수
    # last : 직전 단어의 마지막 단어
    cnt, last = 1, words[0][-1]
    
    for word in words[1:]:
        # 앞 사람이 말한 마지막 단어로 시작하지 않거나 이미 언급된 단어인 경우 종료
        if last != word[0] or dic.get(word):
            return cnt%n+1, cnt//n+1
        last = word[-1]
        cnt += 1
        dic[word] = True
    
    return [0, 0]