프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17684

[나의 풀이]

⌛ 시간 초과 (이후 구현)

def solution(msg):
    answer = []
    
    numbers = { chr(i+64) : i for i in range(1,27)}
    print(numbers)
    
    now = 0
    w_c_cnt = 0
    for i,x in enumerate(msg):
        # print("---------------")
        # print(" i : ", i , " now : ",now)
        w = x
        
        if i==now:
            
            tmp = numbers[x]
            now_add = 0
            # print(" 찾음! : ",w)
            for j,y in enumerate(msg[i+1:]):

                # if i<j:
                w += y
                if w in numbers.keys():
                    tmp = numbers[w]
                    # print(" 찾음! : ",w)
                else:
                    w_c_cnt += 1
                    numbers[w] = 26+w_c_cnt
                    # print(" 추가! : ",w)
                    now += len(w)-1
                    break
            answer.append(tmp)

    # print(answer)
    return answer

압축 알고리즘 중 LZW(Lempel–Ziv–Welch)을 구현하여 문자열을 숫자로 표현하는 문제입니다.

최초 A,B,C..Z 까지 길이가 1인 사전이 기본적으로 제공되고 입력된 문자열의 처음 문자부터 확인하여 사전에 등록된 문자열의 숫자들을 찾아야합니다. 🧸🧸🧸

이때, 사전에 포함된 문자열이 아닐 경우 새로 등록할 수 있어 유의해야하고 사전에 추가한 문자열을 숫자로 변환한 뒤에는 해당 문자열의 크기가 2이상이기 때문에 반복문을 돌때 인덱스(now)를 추가해주어야했습니다.

본 문제를 이해하는데는 어렵지 않았지만 위에서 언급한 인덱스를 추가해주는 부분의 구현이 오래걸려 60분 시간 초과 후 구현하였습니다.🐰🐰🐰

[다른 사람의 풀이1]

def solution(msg):
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    d = {k:v for (k,v) in zip(alphabet, list(range(1,27)))}
    answer = []

    while True:

        if msg in d:
            answer.append(d[msg])
            break
        for i in range(1, len(msg)+1):
            if msg[0:i] not in d:
                answer.append(d[msg[0:i-1]])
                d[msg[0:i]] = len(d)+1
                msg = msg[i-1:]
                break

    print(answer)
    return answer

'나의 풀이'에서 구현하기 가장 까다로운 부분인 인덱스 추가(now)를 따로 변수지정없이 간결히 구현한 풀이입니다.🐳🐳🐳

msg 자체가 사전에 등록되어 있다면 break하고 그것이 아니라면, 입력된 문자열 앞에서부터 사전에 등록되지 않은 문자열을 파악합니다. 이후 등록된 문자열의 숫자를 구하고 등록되지 않은 문자열을 사전에 새로 등록함과 동시에

msg = msg[i-1:]

현재까지 파악한 지점까지 msg 문자열을 초기화 함으로써 어느지점 인덱스까지 파악하였는지 고려하지 않아도 되게하는 풀이였습니다.

[다른 사람의 풀이2]

def solution(msg):
    answer = []
    # 사전 초기화 A~Z
    dic = {chr(i + 64): i for i in range(1, 27)}

    w = c = 0 # 인덱스 초기화
    while True:
        c += 1	
        if c == len(msg):	
            answer.append((dic[msg[w:c]]))
            break
        
        # 만약 [현재글자+다음글자]가 사전에 없다면
        if msg[w:c+1] not in dic:
            dic[msg[w:c+1]] = len(dic) + 1 # 사전에 추가
            answer.append(dic[msg[w:c]])
            w = c	# 현재글자를 다음글자로 옮겨줌
            
        # 만약 [현재글자+다음글자]가 사전에 있다면 w의 값은 변하지 않고 c의 값만 1씩 증가한다. 
    return answer

전체적인 구조는 '다른 사람의 풀이1'과 유사한 방법이되, 인덱스를 초기화하는 부분에서는 '나의 풀이'와 같이 변수에 저장한 방식이였습니다.

또 한가지 포인트로 새로 사전에 등록할 때 len(dic)+1로 표현하여 새로 등록된 문자열의 갯수를 따로 파악하지 않아도 되게 구현한 것을 볼 수 있었습니다.🐤🐤🐤

감사합니다.