Level 2 [3차] 압축 <2018 KAKAO BLIND RECRUITMENT> Python 3

https://programmers.co.kr/learn/courses/30/lessons/17684?language=python3 

코딩테스트 연습 - [3차] 압축

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_%5B3차%5D압축.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from string import ascii_uppercase
from collections import defaultdict

def solution(msg):
    answer = []
    dic = defaultdict(int)
    i = 0
    for c in ascii_uppercase:
        i += 1
        dic[c] = i
    start = 0
    end = 0
    while True:
        word = msg[start:end+1]
        if dic[word] > 0:
            answer.append(dic[word])
            end += 1
            if end >= len(msg):
                break
        else:
            i += 1
            dic[word] = i
            start += (end-start)
            while True:
                end += 1
                if end >= len(msg) or dic[msg[start:end+1]] == 0:
                    end -= 1
                    break
    return answer

---

풀이 과정

풀이 시간 52분

 

from string import ascii_uppercase
from collections import defaultdict

def solution(msg):
    answer = []
    
    #사전
    dic = defaultdict(int)
    
    #사전 인덱스
    i = 0
    
    #알파벳 대문자 사전에 추가
    for c in ascii_uppercase:
        i += 1
        dic[c] = i
        
    #단어의 시작 인덱스 start, 끝 인덱스 end
    start = 0
    end = 0
    
    while True:
    	#현재 단어
        word = msg[start:end+1]
        
        #사전에 있는 단어인 경우,
        if dic[word] > 0:
        	#사전 인덱스를 출력한다
            answer.append(dic[word])
            end += 1
            
            #msg 문자열을 모두 탐색한 경우, 종료
            if end >= len(msg):
                break
                
        #사전에 없는 단어인 경우,
        else:
        	#1 증가시킨 사전 인덱스에 단어를 추가한다
            i += 1
            dic[word] = i
            
            #처리한 단어 이후로 시작 인덱스를 갱신한다
            start += (end-start)
            
            #끝 인덱스를 찾는다
            while True:
                end += 1
                
                #msg 문자열 인덱스를 초과하거나 사전에 있는 가장 긴 단어로 인덱스를 셋팅한다
                if end >= len(msg) or dic[msg[start:end+1]] == 0:
                    end -= 1
                    break
                    
    return answer

#시간복잡도 = O(n^2), 공간복잡도 = O(n^2)

---

참고

• 1. N진수 게임 - 2022.03.30 - [코테 노트/프로그래머스] - Level 2 [3차] n진수 게임 <2018 KAKAO BLIND RECRUITMENT> Python 3

Level 2 [3차] n진수 게임 <2018 KAKAO BLIND RECRUITMENT> Python 3

• 3. 파일명 정렬 - https://hwayomingdlog.tistory.com/312

Level 2 [3차] 파일명 정렬 <2018 KAKAO BLIND RECRUITMENT> Python 3

• 4. 방금그곡 - 2022.03.25 - [코테 노트/프로그래머스] - Level 2 [3차] 방금그곡 <2018 KAKAO BLIND RECRUITMENT> Python 3

Level 2 [3차] 방금그곡 <2018 KAKAO BLIND RECRUITMENT> Python 3

• 5. 자동완성