Python - Recursion으로 구현하는 string compression
Question 2 (20 points) recursion. We want to compress strings that have long sequences of equal characters.
For example, we want to compress "bbbbaaa$$$$$$$$$$$$$$$$d" to "b4a3$16d1". In the compression, each sequence of equal characters is given by the character followed by the length of the sequence. Write function compress to do this. Use no loops; use only recursion. You may use function eqChars of the previous question 1.
Hint: The base case is not necessarily a string with one character.
def eq_chars(s,i):
"""Returns: length of sequence of equal characters starting at s[i].
Examples: eq chars('aaaxxyx',0) is 3 and eq chars('aaaxxyx',5) is 1
Precondition: s is a string, 0 <= i < len(s)."""
def compress(s):
"""Returns: the compression of s, as explained above.
Precondition: s a nonempty string with no digits 0..9."""
암튼 문제는 다음과 같습니다.
간단하게 말해 bbbbaaa$$$$$$$$$$$$$$$$d 를 b4a3$16d1 로 구현하는것이 문제이며
당연히 string에는 숫자가 포함되어있지 않겠습니다.
- 조건
compress 함수를 for나 while같은 loop 없이, 재귀 (recursive function / recursion)로 구현해야 한다.
eq_chars는 for나 while같은 loop를 사용할 수 있으며, 매개변수가 다음과 같이 입력되었을 때 (aaaxxxyx,0) 해당 char가 있는 개수 (3)을 반환한다.
시험시간에 작성한 답안이라 그렇게 깔끔한 코드는 아닌 것 같은데 올려봅니다.
__author__ = "sosal"
def eq_chars(s,i): ## i 위치에서 뒤에 몇개나 같은지만 확인한다.
if s=="": # 만약 string이 존재하지 않으면 "" 리턴
return ""
count = 1 # string이 존재한다면 일단 문자가 하나라도 존재하기 때문에 1이다.
while 1:
if len(s) == i+1: # 현재 위치가 마지막이라면 더이상 뒤의 문자를 확인하지 않는다.
break
if s[i] == s[i+1]: #다음 문자가 같다면 count를 1 증가시키고 index역할을 하는 i도 증가시킨다.
count = count+1
i = i+1
else: # 다음문자와 다르다면 현재 갖고 있는 count를 return 한다.
break
return count
def compress(s):
if s=="": # 아무런 문자가 남지 않으면 "" 값을 리턴
return ""
count = eq_chars(s,0)
return s[0] + str(count) + compress(s[count:])
# 앞쪽에서 시작하는 문자와 연속적인 문자들은 압축해버린 채, 나머지들을 recursive 함수로 보낸다.
if __name__ == "__main__": # main 함수
print(compress('bbbbaaa$$$$$$$$$$$$$$$$d')) # b4a3$16d1
decinc
def eq_chars(s, i):
if s == '':
return 0
if len(s) - 2 < i:
return 1
if s[i] != s[i+1]:
return 1
return 1 + eq_chars(s, i + 1)
eq_chars 함수도 재귀로 쉽게 가능한 코드를 decinc 님이 달아주셨네요
감사합니다 ^^