[이.취.코] [프로그래머스] Chap 12. 구현 - Q9. 문자열 압축

@mildsalmon·2021-09-15 09:28

1. 문자열 압축

난이도
- 중하
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128 MB
출처
- 코딩테스트 연습 - 문자열 압축 | 프로그래머스 (programmers.co.kr)

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안


def solution(s):  
    # pre = s[0]  
    best_len = len(s)  
  
    for i in range(1, len(s)):  
        pre = s[:i]  
        count = 0  
        answer = ''  
        for j in range(0, len(s)+i, i):  
            now = s[j:j + i]  
            if pre == now:  
                count += 1  
            else:  
                if count > 1:  
                    answer = answer + str(count) + pre  
                else:  
                    answer = answer + pre  
                pre = now  
                count = 1  
        if best_len > len(answer):  
            best_len = len(answer)  
    return best_len

a. 회고

내 풀이

단순히 반복하는 방식으로 풀었다. 이런걸 완전 탐색이라고 하던가.

반성

첫 for문에서 range의 end인자부분을 절반까지 줄여도 된다는 것을 생각하지 못했다.

결론

여러번 반복하자.

C. 문제 해설

이해한 내용을 바탕으로 작성했습니다.

중점적으로 생각해야 할 것.
- 문자열을 n개씩 자르면서 몇 번 반복되는지 확인하는 것.
- 문자열 반복을 확인하기 위해 이전 문자열과 현재 문자열을 비교하는 것.
  - 문자열이 같으면 어떻게 처리할지
  - 문자열이 다르면 어떻게 처리할지
책에서는 aabbaccc에서 이전 문자열과 현재 문자열이 같은데 for문이 끝나서 문자열을 합치지 못할 때를 대비해서 for문 밖에도 if count > 1: ~ else: ~를 추가해주었다.
- 나는 for문을 무조건 이전 문자열과 다를때까지 반복시켜서 해당 코드를 추가하지 않았다.