[Python] 프로그래머스 2020 KAKAO 코딩테스트 - 문자열 압축

- 문제 설명

지문이 길어 아래의 링크로 자세한 문제 설명을 대신합니다.

programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

---

주어진 문자열을 조건에 맞게 압축하는 문제입니다. 출력 형태는 (숫자)(문자) 순서로 이루어지며 연속된 문자를 압축하는 과정입니다. 아래는 주어진 예시입니다.

s	result
"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

1번 예시의 경우 "aabbaccc"를 이용해 자세한 설명을 덧붙입니다.
문자열을 최대로 나눌 수 있는 토큰의 길이는 len(s)//2 가 됩니다. 그 이상의 수로 나누어 확인하는 것은 무의미합니다.
따라서 "aabbaccc"의 문자열 길이는 "8" 이므로 최대 4의 토큰 길이에서 1씩 감소(3,2,1)하여 문자열 파싱(Parsing)을 수행합니다.

Token 길이	4	3	2	1
결과문자열	aabbaccc	aabbaccc	aabbaccc	2a2ba3c
문자열 길이	8	8	8	7

파싱 토큰 길이에 따라 연속된 문자열이 같다면 숫자로 압축해야합니다. "aa" --> "2a", "ccc" --> "3c"

저의 접근 방법은 다음과 같습니다. 예제 1번을 경우로 접근법을 설명합니다.

• 조건 1) 최대 토큰의 길이는 len(s)//2=4 이므로, 이 값을 기준으로 -1씩 하며 순차 탐색
• 조건 2) 주어진 문자열을 토큰의 길이만큼 파싱하여 연속된 문자열이 같은지 확인
  

    - 조건 2-1. 단, 연속된 문자열은 2개 이상이 될 수 있으므로("ccc"--> "3c") 같지 않은 문자열이 나올때 까지 확인하는 조건문 삽입

• 조건 3) 같은 문자열이라면 count +=1 후 결과 문자열 생성

• 조건 4) 가능한 토큰의 길이 별(4,3,2,1) 결과문자열 List를 모두 생성 후 이들의 Length를 구함
• 조건 5) Length에서 minimum value 를 추출

---

전체 조건을 만족하는 코드는 아래와 같습니다.
효율적이지는 않지만 조건을 직관적으로 해석하며 구현해본 코드입니다.
생각을 코드로 옮겨내는 연습이 더 많이 필요한것 같습니다. 

def solution(s):
    result_list=[] # 결과 문자열 List
    if len(s)==1: return 1 # 길이가 1인 경우 그냥 1로 출력
    for token_length in range(len(s)//2, 0, -1): # 조건 1
    	# 1개씩 토큰, 2개씩 토큰.... len(s)//2 만큼 토큰길이 설정
        count=1 
        result="" # 결과 문자열
        copy_s=s # 문자열 초기화
        for _ in range(len(s)//token_length+1):
            while True: # 조건 2-1, 같지 않은 문자열이 나올때까지 탐색
                temp_str = copy_s[:token_length]
                comp_str = copy_s[token_length:token_length*2]
                copy_s = copy_s[token_length:] # 문자열 sliding window 방식 탐색
                if len(comp_str) != token_length: break # token_length가 len(s)의 약수가 아닌 경우
                if temp_str == comp_str: count+=1 # 조건 3
                else: break # 같지 않은 문자열이 나온 경우 break
            result += (str(count) if count !=1 else "") + temp_str # (숫자)(문자) 형태 결과문자열 생성
            count=1 # count값 초기화
        result_list.append(result) # 결과 문자열 List 생성
    length_list = [len(x) for x in result_list] # 조건 4, 생성된 결과 문자열 List를 length로 반환
    return min(length_list) # 조건 5