1. 문제
- 프로그래머스 문제와 동일함
- 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60057 - 문자를 압축하여 저장하고자 한다.
- ababab를 예로들면, 두 개로 저장할때, 3ab로 가장 압축이 잘된다.
- abcabcdede와 같은 경우는 2개 단위로 압축하면 abcabc2de, 3개 단위로 압축하면 2abcdede, 3개 단위로 압축할 때 가장 짧은 문자열이 된다.
- 문자열을 1개 이상 단위로 압축했을 때, 가장 짧은 것의 길이를 return하도록 함수를 완성하라.
제한사항
- s의 길이는 1이상 1000이하이다.
- s는 알파벳 소문자로만 이루어져 있다.
입출력 예
2. 아이디어
- 못풀어서, 검색을 통해서 참조하고 리뷰하였다.
- 참조 : https://ljhyunstory.tistory.com/18
3. 예제코드
def solution(s):
# 길이가 1이면, 볼거 없이 1이다.
if len(s) == 1:
return 1
# 문자열 자를 길이를 반복문으로 늘려나가면서 전체를 탐색하게 한다.
result= []
for step in range(1, len(s)+1): # 간격은 1부터
# 그 안에서, 첫번째를 우선 슬라이스 해놓고, step을 간격으로
# for j range(step, 전체길이 + step, step) 스텝만큼 잘라서 앞에 잘라 놓은 것과 비교한다.
string = '' # 압축 문자열 모을 것
prev = s[:step] # 첫번째 스텝
cnt = 1 # 기본 prev가 1이니까
for j in range(step, len(s)+step, step): # step 0 이면 에러
# step 부터 , 길이 + 스텝, 스텝 간격, 걱정말라,
# s문자열 리스트 슬라이싱할때, 벗어나도, 에러 안난다. (인덱스는 에러남)
if prev == s[j:j+step]:
cnt += 1 # 앞의 스텝과 같다면, cnt를 올린다.
else : # 앞의 스텝에 해당하는 문자열과 다르면,
if cnt != 1:
# 앞에 잘라놓은 문자열이 반복 된 것이니까,
# 모으는 문자열 + str (숫자) + 잘라놓은 문자열을 더한다.
string = string + str(cnt) + prev # 지금까지 반복된 문자열 압축하여 문자열 저장
else : # 반복이 1이면,
string = string + prev # 모으는 문자열 + 잘라놓은 문자열
prev = s[j:j+step]
cnt = 1
result.append(len(string)) # 압축된 문자열 길이 모으기
# 가장 바깥 반복문이 하나씩 실행되면 문자열이 만들어 진것이니까,
# len으로 길이를 구해서 문자열의 길이를 하나씩 append로 저장한다.
return min(result) # min 저장된 문자열로, 최소값을 출력한다. 4. 배운점
- 리스트에서 인덱스는 범위 초과시 오류나지만, 슬라이스를 했을때는 오류없이 가능한 범위까지만 보여준다.
- 배수를 탐색할때, 끝을 i로 더한것은 다른 사람들이 2로 나눈것과 같은 목적으로 한 것이다.
- 완전 탐색의 경우, 배수단위로 탐색한다면, 길이에 탐색할 간격을 더한것을 끝으로 해주어야 오류 없이 탐색할 수 있다.
참조
- 이것이 취업을 위한 코딩 테스트다 with 파이썬
성장하는 데이터 분석가