[백준/재귀] 1662번: 압축

https://www.acmicpc.net/problem/1662

1662번: 압축

 

문제 상황

K를 한자리 정수라고하고, Q를 0자리 이상의 문자열이라고 합니다.

K(Q)는 Q의 문자열이 K개가 중복된 것을 의미합니다.

예를 들어 12(34) 라면, 이 문자는 13434를 의미하는 것입니다.

 

이렇게 압축되어 있는 문자열을 풀어서, 문자열의 길이를 구하는 문제입니다.

 

풀이 방법

재귀에 속하는 문제이므로 재귀를 사용하려 했으나, 다음과 같이 문자열을 모두 저장하였더니 메모리 초과가 났습니다.

 

1. 문자열을 받아서, 반복문으로 문자를 하나씩 확인합니다.
2. 숫자이면 스택에 저장합니다.
3. 괄호가 열리면, 스택에 가장 마지막에 있는 문자 k 을 가져옵니다. 
   그리고 괄호 뒤에 있는 문자열부터 함수에 집어넣어서 괄호 안에 있는 문자열 subString을 가져옵니다.
   스택에 N * subString 의 문자열을 넣습니다.
4. 괄호가 닫히면, 스택에 있는 문자열을 return 해줍니다.

이미 봤던 문자열을 처리하는 방법에서는 재귀함수 안의 반복문에서 사용하는 index를 넘겨주는 방식을 사용했습니다.

import sys
from collections import deque


def PressNumber(string):
    stack = deque([])

    i = 0
    while i < len(string):
        if string[i]=='(':
            k = stack.pop()
            num, subString =  PressNumber(string[i+1:])
            subInt = list(int(k)* subString)
            stack += subInt
            i += num
            i+=1
        elif string[i] == ')':
            subString = ''.join(stack).strip()
            return i+1, subString
        else:
            stack.append(string[i])
            i += 1
    return 0, ''.join(stack)



input = sys.stdin.readline
num, string = PressNumber(input().strip())
print(len(string.strip()))

 

그래서 재귀를 사용하면서, 위에 처럼 문자 자체를 저장하지 않고 문자열의 길이를 반환하는 재귀를 만들었습니다.

또한, 이미 봤던 문자열에 대해서는 전역변수처럼 배열을 사용하여 처리해 주었더니, 간단한 코드가 되었습니다.

import sys

check = [False] * 50

def PressNumber(idx):
    temp = ''
    count = 0
    for i in range(idx,len(string)):
        s = string[i]
        if(check[i]):
            continue

        check[i] = True
        if(s.isdigit()):
            temp = s
            count += 1
        elif(s == '('):
            subString = string[i+1:]
            subCount = PressNumber(idx+1)
            count = count - 1 + int(temp) * subCount
        else:
            return count
    
    return count

input = sys.stdin.readline
string = input().strip()

print(PressNumber(0))

 

다음은 재귀를 사용하지 않고, stack 을 사용하여 만들었습니다.

import sys
from collections import deque

input = sys.stdin.readline

count = 0
temp = ''

string = input().strip()
stack = deque([])
for i in range(len(string)):
    s = string[i]
    if s.isdigit():
        count += 1
        temp = s
    elif s == '(':
        stack.append((temp, count-1))
        count = 0
    else:
        num, beforeString = stack.pop()
        count = int(num) * count + beforeString

print(count)