[백준 2257] 화학식량

www.acmicpc.net/problem/2257

2257번: 화학식량

s = input()

d = {
    "H" : 1,
    "C" : 12,
    "O" : 16
}

stack = []

for i in s:
    if i in d:
        stack.append(d[i])
    elif i == "(":
        stack.append(i)
    elif i == ")":
        temp = 0
        while True:
            p = stack.pop()

            if p == "(":
                break

            temp += p
        
        if temp == 0:
            continue
        else:
            stack.append(temp)
    else:
        n = stack.pop()
        temp = n*int(i)
        stack.append(temp)

print(sum(stack))

풀이

 

스택 자료구조에 차근차근 덧셈을 해나간다.

규칙은 아래와 같다.

 

• 스택 구조에 하나씩 push한다.
• 빈칸이라면 그냥 push
• 문자라면 숫자로 변환하고 push
• 숫자라면 스택에서 pop 한것과 숫자를 곱한후 다시 push
• 여는 괄호라면 그냥 push
• 닫는 괄호라면 가장 빨리 pop되는 여는괄호까지 모두 pop 한 후, pop한걸 다 더해주고 push

마지막으로 stack에 남아있는 모든 수의 총합을 구해주면 된다.

 

문제유형이 스택이라 생각됐을 경우 pop으로 꺼낸 후 특정 로직을 처리하고 다시 push하는 등의 테크닉을 잘 활용하면 좋다.

 

시간복잡도

문자의 길이가 N 이라면 O(N)만큼의 시간이 든다.