[Python][프로그래머스] 압축 - 2018 KAKAO BLIND RECRUITMENT

 

 

목차

 

 

🫡 Overview

체감 난이도: ★★☆☆☆

소요시간: 50분

문제 레벨: Lv.2 / 문제 유형: 문자열 구현 
풀이 상태:  스스로 해결
추후: 다시 풀어보기

 

---

문제 링크

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

요구사항 분석

문제: 압축해도 정보가 바꾸지 않도록, 무손실 압축하기 
입력: 문자열(1~1000글자) -> 출력: 색인 번호 리스트

사전의 인덱스는 1부터이다. 
1. 사전 초기화(1~26)

input 문자열의 모든 부분 문자열에 대해서 (i -> i+1)
1) 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
2) w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
3) 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
단계 2로 돌아간다.

 
예시1) KAKAO

현재입력 일치문자열(w) 다음글자(c)   출력   사전추가(w+c)  
KAKAO    K        A         11      KA
AKAO.    A        K         1.      AK
KAO      KA       O.        27.     KAO
O        O        -         15      - ** 유의 - 사전안에 w 문자열 이 있을 경우 

 

예시2) TOBEORNOTTOBEORTOBEORNOT

TOBEORNOTTOBEORTOBEORNOT
현재입력                    일치문자열(w) 다음글자(c)   출력   사전추가(w+c)  
TOBEORNOTTOBEORTOBEORNOT    T          O          20.      TO(27)
OBEORNOTTOBEORTOBEORNOT     O          B          15.      OB(28)
BEORNOTTOBEORTOBEORNOT      B          E          2.       BE(29)  
EORNOTTOBEORTOBEORNOT       E          O.         5.       EO(30)
ORNOTTOBEORTOBEORNOT        O         R           15       OR(31)
RNOTTOBEORTOBEORNOT         R                     18       RN(32)
                                                            NO
                                                            OT
TTOBEORTOBEORNOT                                            TT
TOBEORTOBEORNOT           TO           B                    TOB*
BEORTOBEORNOT             BE           O                    BEO
ORTOBEORNOT               OR            T                   ORT
TOBEORNOT                                                   TOBE
EORNOT                                                      EOR
RNOT                      RN                               RNO
OT                        OT            -                   - 

예시3) ABABABABABABABAB

ABABABABABABABAB
현재입력                일치문자열(w) 다음글자(c)   출력   사전추가(w+c)  
ABABABABABABABAB        A           B.       1.       AB(27)
BABABABABABABAB         B           A.       2.       BA(28)
ABABABABABABAB          AB.         A.       27.      ABA(29)
ABABABABABAB            ABA          B       29       ABAB(30)
BABABABAB               BA           B       28       BAB(31)  
BABABAB                 BAB         A.      31.      BABA(32)
ABAB                    ABAB                 30

 

 

 

나의 코드

def solution(msg):
    # 초기 딕셔너리 및 set 만들기 
    alpabets = ['A','B','C','D','E','F','G','H',"I","J","K","L", "M","N", "O","P","Q","R","S","T","U","V",                      "W","X","Y","Z" ]
    substrings = set() # 부분 문자열 담고 있음 
    hash = dict() # 부분 문자열과 번호를 담고 있음
    for i, value in enumerate(alpabets):
        substrings.add(value)
        hash[value] = i+1
    answer = []
    L = len(msg)
    i = 0
    while True:
        # 입력 문자열의 i 번째 요소에 대해서 for 문을 통해 J를 i번째 부터 문자열 끝까지(L-1)까지 늘려가면서 부분 문자열을 찾는다. 
        # 문자열을 전체 훑었을 때 
        j = i # 4,4
        prev = '' # 인덱스 인쇄할 문자열 
        while j<L:
            w = msg[i:j+1] 
            if w in substrings: # w가 기존 문자열 안에 있으면 
                prev = w
            else: # w가 기존 문자열 안에 없으면 
                w_ = w[:-1]
                hash[w] = len(hash)+1 
                substrings.add(w) 
                prev = w_
                break
            j+= 1
        answer.append(hash[prev])
        i = j
        if i >= L:
            break
   
    
    return answer

 

- 시간 오래 걸린 이유

: 처음에 w 문자열을 늘려나가면서 기존에 만든 문자열인지 검사하는 과정에서 알고리즘을 정확하게 짜지 않음. 
-> w의 인덱스의 경우, 새로운 문자열을 생성하든 안하든 무조건 삽입해 줘야하는데 그걸 간과했다!
 
 

---

배운 점/느낀 점

- 문제에서 하란 대로 구현하기
- 간단한 예시라도 처음부터 끝까지 한 번 시뮬레이션해서 내 알고리즘 점검하기