문제
화학식이 주어질 때 분자량을 계산하라. H=1, C=12, O=16이며, 괄호와 숫자 계수를 지원한다.
입력
화학식 문자열이 주어진다.
출력
분자량을 출력한다.
예제
| 입력 | 출력 |
|---|---|
(H2O)2 | 36 |
풀이
스택으로 괄호와 계수를 처리한다.
- H, C, O는 각각 1, 12, 16을 스택에 push한다
- 숫자를 만나면 스택 top에 곱한다
(를 만나면 스택에 표시를 push하고,)를 만나면(까지의 합을 구한다
핵심 아이디어: 스택을 이용하면 중첩 괄호도 자연스럽게 처리할 수 있다.
코드
input = __import__('sys').stdin.readline
sent = input().strip()
stack = []
for i in sent:
if i == "(":
stack.append(i)
elif i == ")":
temp = 0
while True:
ans = stack.pop()
if ans == "(":
break
temp += ans
stack.append(temp)
elif i == 'H':
stack.append(1)
elif i == 'C':
stack.append(12)
elif i == 'O':
stack.append(16)
else:
stack.append(stack.pop() * int(i))
print(sum(stack))복잡도
- 시간: O(N)
- 공간: O(N)