문자열 압축 풀이
코드
def solution(s):
return min(press(s, index) for index in list(range(1, int(len(s)/2) + 1)) + [len(s)])
def press(s, index) :
result = ''
coef = 1
while(len(s) > index) :
piv, s = s[:index]
s = s[index:]
if piv != s[:index] :
result += str(coef) + piv if coef != 1 else piv
coef = 0
coef += 1
result += str(coef)+ s if coef != 1 else s
return len(result)
랜덤여신 , Yang Sang-Ho 님의 코드를 조금 참고하였습니다.
문제에 관하여
알고리즘입니다.
- 알파벳으로 이루어진
s를 계수+알파벳형태로 바꾸기 (exaaabbb->3a3b)- 가장 작게 압축된
s의 길이return
문자열을 원하는 index길이만큼 압축해주는 press(s, index)메서드가 필요합니다.
압축
s를 piv와 s 로 반복해서 나누어 탐색해가며 coef를 늘려가다가 piv와 다른 문장이 나오면 다시 s와 piv로 나누어가며 탐색을 진행합니다.
1번 임에도 정답률이 25% 인것을 보면 만만하게 볼 문제는 아니라는 겁니다. 그리고 실제로도 조금 까다로웠습니다.
def press(s, index) :
result = ''
coef = 1
while(len(s) > index) :
piv, s = s[:index]
s = s[index:]
if piv != s[:index] :
result += str(coef) + piv if coef != 1 else piv
coef = 0
coef += 1
result += str(coef)+ s if coef != 1 else s
return len(result)
Iterable
Iterable이란 단어는 코드 검색을 하다보면 한번쯤은 본적 있으실겁니다. Iter는 이탈리아어로 반복 이라는 뜻을 가지고있습니다.
Iterable은
for문을 이용해 탐색 가능한 객체
라고 볼 수 있습니다. 예를들면 list, dictionary 등등이 있습니다.
파이썬 라이브러리 중에는 이 Iterable 객체를 인자로받는 메서드들이 있습니다. 예를들면 min(), max() 등등 Iterable 객체의 원소를 반복해서 뒤지고, 그 값을 return하는 메서드들이죠. 그래서 이러한 함수에 리스트 내포를 사용한다면 for문으로 4~5줄 나올 코드를 한줄로 마무리할 수 있습니다.
랜덤여신 , Yang Sang-Ho 코드
def solution(s):
return min(press(s, index) for index in list(range(1, int(len(s)/2) + 1)) + [len(s)])
내코드
def solution(s):
answer = len(s)
for index in range(1, int(len(s)/2 + 1)) :
tmp = press(s, index)
if answer > tmp :
answer = tmp
return answer
두 코드는 같은 일을 하는 코드입니다. 차이가 확 들어오죠?
문제를 푸는것보다 다른사람의 코드를 내것으로 만드는것이 훨씬 중요합니다.