[programmers] [3차] 압축 - 2018 KAKAO BLIND RECRUITMENT

<[3차] 압축>

문제(출처: https://school.programmers.co.kr/learn/courses/30/lessons/17684)

 

 

 

문제 풀이

   - my solution

def solution(msg):
    answer = []
    
    # 사전 초기화
    dict={'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21 ,'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
    
    i=0
    idx=27
    while i<len(msg):
        for j in range(i+1,len(msg)+1): 
            if msg[i:j] in dict: # 사전에 있는 값이면
                if j==len(msg): # 마지막 값이면
                    answer.append(dict[msg[i:j]])
                    i=j
                pass
            else: # 사전에 없으면
                answer.append(dict[msg[i:j-1]]) # 색인 번호 추가
                dict[msg[i:j]]=idx # 단어 사전에 등록
                idx+=1
                i=j-1
                break
    return answer

 

 

1) 알파벳 순서대로 dict를 초기화

2) while문을 사용하여 문자열 다 탐색

  2-1) 반복문을 사용하여 사전에서 현재 입력과 일치하는 가장 긴 문자열 w 찾기

  2-2) 사전에 있으면 pass 없으면 단, 마지막 값이면 answer에 색인 번호 추가

  2-3) 사전에 없으면 그 전까지의 색인 번호를 answer에 추가하고, 단어를 사전에 등록

---

생각🤔

 

다 풀고나서 시간 초과가 발생할까 봐 멈칫했지만 모든 테스트를 통과하였다.

dict와 반복문을 사용해서 해결할 수 있는 문제였다.

사전에서 일치하는 가장 긴 문자열을 찾는 방법으로 반복문을 사용하여 그 단어가 

사전에 있으면 pass, 없으면 그 전까지의 단어의 색인 번호를 추가하고, 현재 단어를 사전에

등록하는 방법으로 문제를 해결할 수 있었다.

 

내가 생각하기에 이 문제의 포인트는

1) 사전에서 현재 입력과 일치하는 가장 긴 문자열을 찾는 방법

이었던 것 같다.

---

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges