[LeetCode] Decode String

LeetCode에 "Top 100 liked" 리스트에 수록되어 있는 문제이다. DFS 문제로 분류되는데 국내 기준으로는 구현 문제로 분류될 것 같다. 문제 풀이에 엄청난 시간이 들었는데, 그 만큼 구현 문제에 대한 연습과 대비가 안되어 있다는 걸 느꼈다. 

알고리즘을 설계하기 전에 재귀적으로 접근하면 풀이가 가능할 것으로 예상하고, 재귀적으로 설계를 해나가면서 어려웠던 점은 문자열의 인덱스를 적절히 잘라주는 계산과 예외에 대한 처리였다. 다음에 이 문제를 복습할 때에는 재귀적 접근 뿐만 아니라 스택을 사용해서 접근하는 방법도 고려해봐야겠다.

 

class Solution:
    def decodeString(self, s: str) -> str:
        return self.decode(s)

    def decode(self, s):

        result = ""
        braket_counter = 0
        braket_trigger = False
        
        idx_braket_start = -1
        idx_braket_end = -1
        
        for idx in range(len(s)):
            
            # 괄호 위치 저장
            if s[idx] == "[":
                braket_counter += 1
                if idx_braket_start == -1:
                    idx_braket_start = idx
            elif s[idx] == "]":
                braket_counter -= 1
                idx_braket_end = idx
            
            # 괄호 끝에 도달했다면
            if braket_counter == 0 and idx_braket_start != -1 and idx_braket_end != -1:
                braket_trigger = True
                
                # 숫자위치 저장
                idx_digit = idx_braket_start - 1
                while s[idx_digit].isdigit():
                    idx_digit -= 1
                idx_digit += 1
                                    
                head = s[:idx_digit]
                tail = s[idx_braket_end + 1:]
                digit = s[idx_digit:idx_braket_start]

                # 재귀적으로 decode 수행
                decoded_substr = self.decode(s[idx_braket_start + 1:idx_braket_end]) * int(digit)
                
                # 처리도중 [ 가 들어있다면 []에 감싸져 있지 않은 문자열을 빼낸다.
                if "[" in head:
                    idx_head = 0
                    for idx in range(len(head)):
                        if head[idx] == "]":
                            idx_head = idx
                    head = head[idx_head+1:]
                if "]" in tail:
                    tail = ""
                
                # 결과값 도출
                result += head + decoded_substr + tail                
                
                idx_braket_start = -1
                idx_braket_end = -1
        
        if braket_trigger:
            return result
        else:
            return s

 

구현문제는 medium 수준의 난이도라면 print로 결과값을 찍어가면서 억지로라도 문제를 풀이할 수 있을 거 같다. 두려워 하지 말고 차근차근히 중간결과값을 따라가면서 오류를 따라가자!