[LeetCode]Decode String

https://leetcode.com/problems/decode-string/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 문자열을 패턴에 알맞게 디코딩하는 문제입니다. 숫자가 나오면 [] 안에 위치한 문자를 반복합니다.

 

처음 시도한 답안

class Solution(object):
    def decodeString(self, s):
        stack = []
        curr_string = ''
        curr_number = 0

        for char in s:
            if char == '[': # 여는 괄호면
                stack.append(curr_string) # 현재까지의 문자와
                stack.append(curr_number) # 등장한 숫자를 스택에 넣음
                curr_string = '' # 그리고 초기화
                curr_number = 0

            elif char == ']': # 닫는 괄호면
                number = stack.pop() # 반복 횟수를 뺴고
                prev_string = stack.pop() # 이전까지의 문자를 빼고
                curr_string = prev_string + (curr_string) * number # 이전 문자 + 현재 문자 * 숫자로 업데이트

            elif char.isdigit(): # 숫자를 만나면 반복횟수 기록, 10의 자리 이상인 경우를 대비해 *10이 필요
                curr_number = (curr_number * 10) + int(char)
            else: # 알파벳을 만나면 현재 문자에 더하기
                curr_string += char

        return curr_string

접근 방법

1. 기본적으로 스택을 활용합니다.
2. 현재까지의 문자를 기록하는 curr_string, 현재까지의 숫자를 기록하는 curr_number 변수를 이용합니다.
3. 주어진 문자열을 순회합니다.
4. 여는 괄호를 만난 경우라면
   1. 현재까지의 누적 문자와(스택에 넣으면 이전까지의 누적문자가 됨) 등장한 숫자를 스택에 넣습니다.
   2. 문자와 반복횟수를 초기화합니다.
5. 닫는 괄호를 만난 경우라면
   1. 스택에서 pop을 2번하여 등장했던 숫자와 이전까지의 누적 문자를 가져옵니다.
   2. 현재 문자는 = 이전 문자 + (현재까지의 누적 문자 * 등장했던 숫자) 로 업데이트 합니다.
      숫자는 스택을 넣는 행위("[" 문자 앞에 등장하므로)전에 기록이 되므로 현재까지의 누적 문자와 곱하는 것입니다.
6. 숫자를 만난 경우라면
   1. 숫자를 기록합니다. 10의 자리 이상이 등장할 수도 있으므로(숫자가 2번 연속 등장하는 경우) *10이 필요합니다.
7. 알파벳을 만난 경우라면
   1. 현재 문자에 등장한 char를 누적합니다.
8. 반복을 종료하면 디코딩된 문자를 얻을 수 있습니다.

가장 중요한 포인트는 [를 만날때 그전까지의 누적 문자열과 [ 앞에 등장한 숫자를 스택에 추가하는 것입니다. 그리고 ]를 만나게 되면 이전까지의 누적 문자열(pop) + 현재까지의 누적문자열 * 등장한 숫자(pop)을 통해 풀이가 가능합니다.

 

이 문제를 풀이할 때 스택을 사용하면 될 것이라는 아이디어까지는 생각할 수 있었습니다. 스택에 누적 문자열과 숫자를 기록하면서 이어 붙이는 방식으로 디코딩을 진행하려 했으나, nested로 이루어진 괄호에서 발생하는 여러 케이스를 커버할 수 없었습니다.

 

특정 문제를 접할때 어떤 알고리즘을 활용 해야겠다는 것까지는 잘 떠올르는 것 같은데, 예외 케이스를 커버하거나 구현하는 부분에서 발목이 많이 잡히는 것 같습니다. 특정 시간을 고민해보다가 풀리지 않으면 최대한 다른 솔루션과 해설들을 많이 보고 접하면서 체득시키는 방법이 필요할 것 같습니다.