알고리즘
자료구조
[1662] 압축
by Hwang
문제
https://www.acmicpc.net/problem/1662
풀이
압축된 문자열의 오른쪽부터 왼쪽 방향으로 스택을 이용해서 개수를 구해주었다.
오른쪽부터 왼쪽 뱡향으로 읽기 때문에 문자가 ‘)’ 일 때 괄호가 열리고, 괄호가 열릴 때 스택에 해당 괄호안에 있는 문자의 개수를 넣어 준다. 물론 아직 문자가 없기 때문에 0을 넣어준다.
문자가 숫자일 때 열린 괄호가 있다면 스택의 가장 상단에 있는 문자의 개수에서 1을 더 해준다. 여기서 스택의 모든 값을 갱신해주지 않아도 된다. 나중에 괄호가 닫힐 때 값을 아래로 보낼 것이다. 다음으로 열린 괄호가 없는 경우에는 결과 값에 1을 더해준다.
문자가 ‘(’ 일 때 스택의 가장 상단에 있는 문자의 개수를 꺼내준다. ‘(’가 나오고 나서는 반복한 개수가 나오고, 이 개수를 꺼낸 문자의 개수와 곱하면서 압축을 푼 문자의 개수를 구해준다. 만약 열린 괄호가 아직 존재하면 스택의 가장 상단의 문자의 개수에 더해주고, 존재하지 않는다면 결과 값에 더해준다.
import sys
S = sys.stdin.readline().strip()
stack = []
result = 0
index = len(S) - 1
while index >= 0:
if S[index] == ')':
stack.append(0)
elif S[index] == '(':
top = stack.pop()
count = top * int(S[index - 1])
if stack:
stack[-1] += count
else:
result += count
index -= 1
else:
if stack:
stack[-1] += 1
else:
result += 1
index -= 1
print(result)
Comment