문자열 압축 해제문제로 살펴본 INTP와 재귀 알고리즘의 상관관계

조건) 
n{알파벳_문자열} -> 알파벳_문자열을 n번 만큼 반복

예시)
2{ac}f -> 2acacf
e2{t3{b}}v -> etbbbtbbbv

 
- 재귀 알고리즘을 통하여 문제를 풀어보았습니다.
 
코드를 보기 전에,

 

재귀 알고리즘에 대해 간단히 알아볼까요?

 

 

일차적으로 재귀 알고리즘의 논리적 구조는 반복문과 같습니다.

따라서, 재귀 알고리즘으로 풀 수 있는 문제는, 반복문으로 풀 수가 있는데요,

익숙한 반복문 대신 재귀로 문제를 풀었을 때의 장점은 무엇일까요?

 

-> 변수 저장을 위해 스택이 필요한 상황에서

-> 스택을 직접 생성하는 방식 대신에 메소드 콜을 통한 프로그램의 스택 메모리를 사용하기 위해서입니다.

 

간단하게 들어도, 무언가 귀찮은 작업들을 재귀를 통해서 해결할 수 있을 것 같은 느낌이죠?

 

- 바로 이러한 점에서, 
재귀 알고리즘은 마치 제 MBTI 성향인 INTP를 닮았습니다.
 
특정한 작업을 대신(스택, 변수 생성), 나중에(재귀호출복귀) 처리하려는 재귀 알고리즘은
중요한 일을 미래의 나에게 맡기는 INTP의 성향과 흡사합니다.
 

 

 
- 재귀 알고리즘은 메모리 스택을 활용함으로써 특정 작업을 수행하고 호출된 그 곳으로 돌아와 예정된 작업을 수행합니다..
((집돌이인 INTP와 매우매우 흡사하죠 .. )
 
 
 
이렇게 재귀 알고리즘의 특성을 알아보았는데요.. 
이제 코드를 살펴볼까요 ..?
 

public class INTP {

    public static void main(String[] args) {
        String code1 = "3{he2{l}o}friend";
        System.out.println(recur(1, code1)); // hellohellohellofriend

        String code2 = "f2{a3{bc}}z"; 
        System.out.println(recur(1, code2));  // fabcbcbcabcbcbcz
    }

    public static String recur(int multiply, String code) {
        // 숫자 제외 재귀 넣고
        // 나오면 } 찾아서 x번 반복해여 붙이기
        String before = "";
        String after = "";
        for (int i = 0; i < code.length(); i++) {
            if (Character.isDigit(code.charAt(i))) { // 문자가 숫자일 경우 -> 재귀 조건
                int nextMultiply = code.charAt(i) - '0';
                before = code.substring(0, i);
                after = recur(nextMultiply, code.substring(i + 2));

                code =  before + after;
            }

            if(code.charAt(i) == '}'){ // 문자가 } 인 경우 -> 종료 조건
                String multipledTarget = multiplyTarget(multiply, code.substring(0, i));
                return multipledTarget + code.substring(i + 1);
            }
        }

        return code;
    }

    public static String multiplyTarget(int mutiply, String target){
        String returnStr = "";
        for (int i = 0; i < mutiply; i++) {
            returnStr += target;
        }
        return returnStr;
    }
}

 

 

- 크게, 재귀가 호출되는 코드와, 재귀가 종료되는 코드 두 부분으로 나누어서 살펴보겠습니다.

if (Character.isDigit(code.charAt(i))) { // 문자가 숫자일 경우 -> 재귀 조건
    int nextMultiply = code.charAt(i) - '0';
    before = code.substring(0, i);
    after = recur(nextMultiply, code.substring(i + 2));

    code =  before + after;
}

문자열을 순회하다, 숫자를 발견하게 되면 해당 '숫자'와, '{' 을 제와한 문자열을 파라미터에 넣고 재귀함수를 호출합니다.

 

따라서 각 메소드 스택에선, 몇번 반복해야할지를 나타내는 multiply, 어떤 문자열을 반복해야할지를 나타내는 code를 순서대로 생성하게 됩니다. 실제로 처리해야할 로직은 아직 미뤄둔 상황이라고 볼 수 있습니다.. ㅎㅎ 

 

 

- 다음으로 재귀 알고리즘에서 중요한 종료조건에 대해서 알아봅시다. 

재귀는 반복문과 같은 구조기에, 종료조건을 잘 설정해주는 것이 중요합니다. 

if(code.charAt(i) == '}'){ // 문자가 } 인 경우 -> 종료 조건
    String multipledTarget = multiplyTarget(multiply, code.substring(0, i));
    return multipledTarget + code.substring(i + 1);
}

위의 종료조건 코드에선 '}'라는 문자를 만나면 특정 작업을 수행하게 하였는데요,

code로 전달받은 현재 문자열에서, '}' 문자 바로 이전까지를 multiply번 반복하여 이어붙이고, 

마지막으로 '}' 이후의 문자열을 이어붙이고 있습니다. 

그림으로 표현해보자면 이렇게 그려볼 수 있을 것 같습니다.

왼쪽 메소드 콜스택에 multiply와 code 변수가 쌓이면서 재귀 호출 후,

스택 복귀하여 해당 변수들로 문자열 반복 후 이어붙이기 작업을 하고 리턴을 하고 있는 것을 확인해볼 수 있습니다.