[PART3] 9. 문자열 압축

코뉴·2021년 1월 14일

이코테: 문제풀이

목록 보기

15/28

알고리즘 유형별 기출문제: 구현

💻 9. 문자열 압축

📌2021/01/14 작성 코드

# 압축 단위는 1 ~ len(s)//2 까지 테스트를 해본다.
# len(s)//2까지인 이유: 압축을 위해서는 문자열을 제일 앞부터 정해진 길이만큼 잘라야 한다.
# 압축, 즉 '줄인다' 라는 것에 초점을 맞추면, 이 연속된 문자열이 2번 이상 등장할 때에만 의미가 있다.
    
def solution(s):
    length = len(s) # 문자열의 길이
    # 문자열 길이가 1
    if length == 1:
        return length
    # 길이 2 이상
    answer = length # answer의 초기값은 length
    for i in range(1, length//2+1): # i = 압축 단위 수
        '''
        print('압축단위수:',i)
        '''
        # 변수들 초기화
        prev = s[0:i]
        now = ""
        pointer = i
        count = 1
        temp_str = ""
        # 문자열 검사
        while pointer <= length : # 인덱스가 유효한 범위 내에 있도록
            now = s[pointer: pointer+i]
            '''
            print('now:', now, 'prev:', prev, 'pointer:', pointer)
            '''
            # prev와 now가 다를 때
            if prev != now:
                # 만약 count가 1보다 크면 temp_str에 concatenate
                if count > 1:
                    temp_str += str(count)
                # prev를 temp_str에 concatenate
                temp_str += prev
                # count 초기화
                count = 1
            # prev와 now가 같을 때
            else:
                count += 1 # count만 증가
            # pointer 재설정
            pointer += i
            # prev 재설정
            prev = now
        # while 빠져나온 뒤, now 값도 넣어줘야 한다
        temp_str += now
        # 완성된 temp_str의 길이와 answer 비교
        '''
        print('temp_str:', temp_str)
        '''
        if len(temp_str) < answer:
            answer = len(temp_str)
        # temp_str 초기화
        temp_str = ""

    return answer

💭 아이디어

압축 단위는 1 ~ len(s)//2 까지 테스트를 해본다.
len(s)//2까지인 이유: 압축을 위해서는 문자열을 제일 앞부터 정해진 길이만큼 잘라야 한다.
압축, 즉 '줄인다' 라는 것에 초점을 맞추면, 이 연속된 문자열이 2번 이상 등장할 때에만 의미가 있다.

🤓 문제 해설

이 문제 또한 요구하는 대로 충실히 구현만 하면 정답 판정을 받을 수 있다. 입력으로 주어지는 문자열의 길이가 1,000 이하이기 때문에 가능한 모든 경우의 수를 탐색하는 완전 탐색을 수행할 수 있다.

예를 들어 길이가 N인 문자열이 입력되었다면 1부터 N/2까지의 모든 수를 단위로 하여 문자열을 압축하는 방법을 모두 확인하고, 가장 짧게 압축되는 길이를 출력하면 된다.

🤓 답안 예시

def solution(s):
    answer = len(s)
    # 1개 단위(step)부터 압축 단위를 늘려가며 확인
    for step in range(1, len(s) // 2 + 1):
        compressed = ""
        prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출
        count = 1
        # 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
        for j in range(step, len(s), step):
            # 이전 상태와 동일하다면 압축 횟수(count) 증가
            if prev == s[j:j + step]:
                count += 1
            # 다른 문자열이 나왔다면(더 이상 압축하지 못하는 경우라면)
            else:
                compressed += str(count) + prev if count >= 2 else prev
                prev = s[j:j + step] # 다시 상태 초기화
                count = 1
        # 남아있는 문자열에 대해서 처리
        compressed += str(count) + prev if count >= 2 else prev
        # 만들어지는 압축 문자열이 가장 짧은 것이 정답
        answer = min(answer, len(compressed))
    return answer