카카오 코딩테스트 - 압축

array.index(key) 하면 배열 내의 index를 반환해준다.

하지만 배열이라 하나씩 체크해가며 비교해야하니 O(n)이다.

다른 사람의 풀이를 보니 아예 key를 문자열로, value를 index로 한 dictionary를 선언해서 쓰던데

시퀀셜하게 저장하고 그 index를 가져와야하니 배열로 해도 되지만,

역으로 그 index를 문자열로 접근해 가져와야하니 dictionary로 만들어 O(1)의 시간으로 접근하는게 나은 것 같다.

그리고 처음에는 start, end의 index로 하지 않고 start에 i를 추가해가며 start+i를 사용했는데,

파이썬의 배열[s:e]가 사실 s~e-1로 슬라이싱해주다 보니 1씩 더하고 빼는게 좀 헷갈리는것같다

차라리 e를 계산해두고, 슬라이싱할 때 e+1로 쓰는 게 덜 헷갈리고 안정적인것같다. 

def solution(msg):
    answer = []
    dic = [-1]
    for i in range(26):
        dic.append(chr(65 + i))
    s, e = 0, 0
    l = len(msg)

    while s < l and e < l:
        if msg[s:e + 1] in dic:  # 사전에 있음
            e += 1
            if e == l:
                answer.append(dic.index(msg[s:e])) # 끝나는데 사전에 있으면
                break
        else: #사전에 없음
            dic.append(msg[s:e+1])
            answer.append(dic.index(msg[s:e])) # 그 전에꺼
            s=e


    return answer