Python - Recursion으로 구현하는 string compression

 

/*

 * http://sosal.kr/
 * made by so_Sal
 */

 

 

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

2015/06/09 15:03

 

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 님이 달아주셨네요

감사합니다 ^^