[구현] 09.문자열 압축 (유형별 기출문제, 이것이 코딩테스트다 with 파이썬)

구현 개념

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 것

동일한 알고리즘이면 더 간결하고 효율적인 코드가 잘 작성된 코드

아이디어 떠올리는 것과 별개로 구현 능력은 실무에서도 매우 중요

 

유형

완전 탐색

• 모든 경우의 수를 빠짐없이 다 계산하는 해결 방법
• 모든 경우의 수를 다 계산
• 반복문 혹은 재귀 함수를 적절히 사용하여 예외 케이스 모두 확인
• 일반적으로 DFS/BFS 알고리즘 이용

시뮬레이션

• 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형
• 완전 탐색과 해결 방법 비슷, 복잡한 구현 요구사항을 그대로 코드로 작성

원소를 나열하는 모든 경우의 수를 고려해야 하는 상황에서 보통 순열이나 조합 라이브러리 사용

→ 파이썬 표준 라이브러리 itertools로 쉽게 구현

 

문제

* 문자열은 제일 앞부터 정해진 길이만큼 잘라야 함!!! 유의하기!!!

 

해설

문제에서 요구하는 대로 충실히 구현만 하면 정답 판정

입력 문자열 길이 1,000 이하이므로 완전 탐색(모든 경우의 수 탐색)

예) 길이가 N인 문자열 → 1~N/2의 모든 수를 단위로 문자열을 압축하는 방법 모두 확인, 가장 짧은 압축 길이 출력

 

이와 같이 step4 ~ step6에 마찬가지로 수행하면 됨

위의 경우 '문자열을 3개 단위로 잘랐을 때' 문자열 길이가 7로 가장 많이 압축

 

풀이

# 프로그래머스 사이트에서 테스트해야 정상 동작
# https://school.programmers.co.kr/learn/courses/30/lessons/60057

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

 

해석

 

변수 : 문자열 길이 answer, 압축완료 문자열 compressed, 반복 문자열 prev, 문자열 반복 횟수 count, 반복 단위 step

 

1. 문자열 길이 answer 초기화

------------------------------------ 반복문 : step in 1~문자열 길이//2 ------------------------------------

2. 압축완료 문자열 compressed 초기화

3. 반복 문자열 prev 추출 : 앞 ~ step 까지의 문자열 & count += 1

4. 반복문 : j in 반복 문자열 prev 이후~끝, step의 간격으로

ㄴ j가 prev와 일치 : count +=1

ㄴ j가 prev와 일치하지 않는 문자열 등장 : 압축완료 문자열 compressed + 횟수 + 반복 문자열 prev

                                                                   근데, count가 1이면 그냥 prev만 쓰기

                                                                   반복 문자열 prev 업데이트 & count를 1로 초기화

5. 반복문 이후 잔류 문자열에 대한 처리

ㄴ 압축완료 문자열 compressed + 횟수 + 반복 문자열 prev

     근데, count가 1이면 그냥 prev만 쓰기

6. 문자열 길이 answer 최솟값으로 업데이트