1662번: 압축
압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이
www.acmicpc.net
- 문제 설명 -
압축은 K(Q)은 Q * K를 의미합니다. 즉 3(5) = 555 가 됩니다.
K는 한자리 정수입니다. 그렇기 때문에 53(5) = 5가 53개 있는 것이 아니라 5 + 3(5) , 5555 가 됩니다.
압축되지 않은 문자열의 길이를 출력해야 하는데, 주의해야할 점은 압축되지 않은 문자열의 길이가 무려 21억이라는 것
복습할 문제 선정 이유 :
- 압축되지 않은 문자열의 길이가 터무니 없게 높게 주어진 경우, 문자열을 압축해제 해서 풀어나가며 진행할 경우 시간도 오래 걸리고 메모리도 많이 사용하게 됩니다
- 이런 특별한 경우를 처리 할 수 있는 방법을 생각해내야 하는 문제는 처음 보는 문제였기에 이 방법을 익혀두기 위해 복습할 문제로 선정하였습니다.
** 코드는 더 보기 칸을 눌러서 확인해주세요 **
1. 압축되어있는 문자열을 압축되지 않은 상태로 되돌리기
- 괄호 안에 있는 숫자를 여는 괄호 바로 앞에 있던 숫자만큼 곱해줍니다. 괄호 안에 다시 괄호가 나올 경우 계속 괄호 앞쪽의 숫자를 체크하는 것이 번거롭기 때문에, 뒤쪽에서부터 탐색을 해줍니다.
- 뒤쪽에서부터 탐색을 하면 닫는 괄호가 나올때마다 스택에 담아주고 여는 괄호 다음의 숫자가 나오면 바로 바로 곱해주면서 풀어주면 되기 때문입니다.
- 여는괄호 다음에 나오는 숫자부터 닫는괄호 전까지의 숫자까지!!
더보기
S = input()
stack = []
N = len(S)
for i in range(N-1, -1, -1) :
stack.append(S[i]) #뒤에서부터 일단 스택에 넣기
if i == N-1 : continue
# ) 가 나왔을 경우 앞으로 나올 값들은 (가 나온 이후의 숫자에 곱하기를 해줄 것
if S[i+1] == "(" : # ( 다음에 숫자가 나왔을 경우 ) 가 나올때까지의 숫자들을 현재 값에 곱하기해줄것
s = ""
stack.pop() # 현재 숫자가 스택에 들어가 있을테니 빼주고
stack.pop() # 그 다음은 여는 괄호이니 다시 빼준 뒤
while stack :
n = stack.pop() #그 다음 숫자부터 반복문을 돌리기
if n == ")" : # 스택에 )가 나올때까지 돌려야함
break
else :
s = s + n
s *= int(S[i])
stack.append(s) # 다음 괄호를 대비해서 스택에 문자열 다시 넣어두기
2. 문자열을 압축된 상태로 무턱대고 되돌릴 경우 길어지는 문자열, 시간초과 or 메모리 초과의 위험성 증가
- 우리가 필요한 건 문자열 전체가 아니라 문자열의 길이입니다.
- 100000000000000000000000000000 이라는 문자가 있다면 우리는 이 문자열이 필요한게 아니라 길이 30 필요하다는 걸 생각해야합니다
- 압축을 풀 때 굳이 압축이 풀린 문자열을 넣는게 아니라 문자열의 길이를 넣어주면 이 문제를 해결할 수 있습니다.
- 여는 괄호가 나왔을 때 처리해주는 부분을 살짝 바꿔보도록 하겠습니다.
더보기
if S[i+1] == "(" :
s = 0 # s는 이제 문자열을 받는게 아니라 문자열의 길이를 받을 것
stack.pop()
stack.pop()
while stack :
n = stack.pop()
if n == ")" :
break
else :
if type(n) == str : # 괄호 이후 문자열이 나올 때마다 길이 1 증가
s += 1
else : # 문자열이 아니라면 구해놓은 길이가 나온것이므로 그만큼 증가
s += n
stack.append(s * int(S[i])) # 길이를 모두 구했으면 다음 괄호를 대비해 다시 스택에 넣어두기
3. 괄호가 모두 끝났다면 기존에 남아있는 문자열이 계속해서 stack에 들어갔을 것이므로 stack에 있는 값들을 한 번 정리해줍니다. (기존에 주어지는 S의 길이는 50이기 때문에 stack에 들어있는 값들을 빼주는 건 큰 문제가 없습니다)
최종 코드
S = input()
stack = []
N = len(S)
for i in range(N - 1, -1, -1):
stack.append(S[i])
if i == N - 1:
continue
if S[i + 1] == "(":
s = 0 # s는 이제 문자열을 받는게 아니라 문자열의 길이를 받을 것
stack.pop()
stack.pop()
while stack:
n = stack.pop()
if n == ")":
break
else:
if type(n) == str: # 괄호 이후 문자열이 나올 때마다 길이 1 증가
s += 1
else: # 문자열이 아니라면 구해놓은 길이가 나온것이므로 그만큼 증가
s += n
stack.append(s * int(S[i])) # 길이를 모두 구했으면 다음 괄호를 대비해 다시 스택에 넣어두기
ans = 0
while stack:
n = stack.pop()
if type(n) == int:
ans += n
else:
ans += 1
print(ans)