[파이썬/python] 백준 - 17287 The Deeper, The Better

문제

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

---

문제 설명

1. 대괄호, 중괄호, 소괄호, 0에서 9까지의 숫자로 이루어진 문자열 S가 주어진다.
2. 문자열 S에 포함된 숫자들은 점수를 휙득하게 된다.
   1. 대괄호 안에 있는 숫자는 3점
   2. 중괄호 안에 잇는 숫자는 2점
   3. 소괄호 안에 있는 숫자는 1점
3. 한 숫자가 여러 개의 괄호 안에 있는 경우 각 괄호의 점수를 합한 값이 그 숫자의 점수이다.
   1. 이 때 같은 숫자가 여러 개 있더라도 위치가 다르면 점수를 따로 계산한다.
4. 나올 수 있는 높은 점수를 출력한다.

---

풀이

스택을 통해 괄호를 제거해가면서 숫자가 나왔을 때 스택에 존재하는 괄호의 수 만큼 점수를 넣어주면 된다.

이 때 숫자가 여러 개 존재할 때 각각 점수를 다르게 넣어준다는 점이 이 문제의 포인트인 것 같다.  

1. scores 딕셔너리에 키, 밸류로 각 괄호의 점수를 초기화한다.
2. 문자열을 순회한다.
   1. 왼쪽 괄호일 때 stack에서 제거한다.
   2. 오른쪽 괄호일 때 stack에서 삽입한다.
   3. 숫자일 때 현재 stack의 괄호 별 점수를 더한 후 최댓값을 갱신한다.
3.  최댓값을 출력한다.

---

코드

import sys
input = sys.stdin.readline

res = 0
s = input().strip()
stack = []
num = []
scores = {']': 3, '}': 2, ')': 1}
for i in range(len(s)-1,-1,-1):
    if s[i] in [']',')','}']:
        stack.append(s[i])
    elif s[i] in ['[','(','{']:
        stack.pop()

    else:
        tmp = 0
        for s2 in stack:
            tmp += scores[s2]
        res = max(res,tmp)
print(res)

---

시간복잡도

• 총 문자열의 길이만큼 순회하므로 길이를 N으로 하면 $O(N)$이다.
• N은 최대 100이므로 약 $O(100)$의 시간복잡도가 소요된다.