문제 바로가기

solution

def solution(msg):
    def getnum(char):
        return ord(char)-ord('A') + 1
    added = []
    printed = []
    i = 0
    while i < len(msg):
        k = i + 1
        while k < len(msg) and msg[i:k+1] in added:
            k+=1
        if k == i+1:
            printed.append(getnum(msg[i]))
        else:
            printed.append(added.index(msg[i:k])+27)
        added.append(msg[i:k+1])
        i=k
    return printed

getnum : ABCD-Z 를 각각 1,2,3,26 으로 바꾸는 함수

chars = {chr(64+e): e for e in range(1,27)}

이런식으로 하기도 하더라. ㄷㄷ
나는 added 에 추가하고, 그 index 를 이용하여 색인 번호를 찾았는데 dictionary 를 이용하여 바로 사전 글자를 key 로 넣어 하기도 했다. 리스트에서 index 찾는 것보다 딕셔너리에서 바로 key - value 값 찾고 가져오는 게 더 빠르다.

https://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table
실제로 dictionary 와 list 에서 item 을 찾을 때의 efficiency 에 대한 논의들.
list 가 O(n) 이라면 dictionary 는 O(1). 심지어 set 은 dictionary 보다 더 빠르다고.

string key 만 가지는 dictionary 에게는 fast-path 도 있다한다.

해시 테이블이 빠른 이유는?
저장할 때 key 값에 해시 함수를 적용해 고유한 index 를 만들어 저장하기 때문. key 를 알면 해시 함수를 통해 바로 index 를 알 수 있으므로 데이터를 찾을 때 O(1) 의 평균 시간복잡도로 삭제, 조회 등이 가능하다.