[Programmers] 문자열 압축 (문자열 Lv.2) - Python

1. 문제

---

게임 맵 최단거리

2. 풀이

---

코드

def solution(s):
    answer = len(s)  # 최소 길이로 초기화

    # 1부터 문자열의 절반까지 단위 길이로 압축을 시도
    for step in range(1, len(s) // 2 + 1):
        compressed = ""
        prev = s[0:step]  # 이전 문자열
        count = 1  # 반복 횟수

        # step부터 문자열의 끝까지 step 단위로 확인
        for j in range(step, len(s), step):
            # 이전 문자열과 동일한 경우
            if prev == s[j:j + step]:
                count += 1
            else:
                # 이전 문자열이 반복된 횟수와 함께 compressed에 추가
                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를 비교하여 더 작은 값으로 갱신
        answer = min(answer, len(compressed))

    return answer

입력 및 출력

s = "aabbaccc"	

>> 7

3. 로직

---

1. 변수명 변경

• answer를 최소길이로 초기화한다.

2. 압축 단위별로 반복

• 1부터 문자열의 절반까지의 길이를 단위로 압축을 시도한다.

3. 압축 로직

• 압축된 문자열을 담을 compressed 변수를 초기화한다.
• 현재 검사 중인 이전 문자열을 prev로 지정한다.
• 반복 횟수를 나타내는 count 변수를 1로 초기화한다.

4. 문자열 검사

• 단위 길이부터 문자열의 끝까지 단위별로 확인한다.
• 현재 검사 중인 부분 문자열이 이전 문자열(prev)과 동일한 경우, count를 증가시킨다.

5. 문자열 처리

• 현재 검사 중인 부분 문자열과 이전 문자열(prev)이 다른 경우, 이전 문자열을 압축된 문자열(compressed)에 추가한다.
• 만약 count가 2 이상인 경우, 압축된 문자열에는 반복된 횟수와 함께 추가된다.

6. 남은 문자열 처리

• 문자열 검사가 끝난 후, 남은 부분 문자열에 대해서 처리한다.
• 만약 count가 2 이상인 경우, 압축된 문자열에는 반복된 횟수와 함께 추가된다.

7. 최소 길이 갱신

• 압축된 문자열의 길이와 최소길이(answer)를 비교하여 더 작은 값으로 최소길이를 갱신한다.

8. 결과 반환

• 최소길이를 반환한다.

4. 그림

---