문제
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
- 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
- X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
- ‘()’ 인 괄호열의 값은 2이다.
- ‘[]’ 인 괄호열의 값은 3이다.
- ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
- ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
- 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
예제.
입력 : (()[[]])([])
출력 : 28
★ 시작하기 전에..
결론은 못풀었다. 아래는 나의 풀이가 아니다. 멋지게 풀었다고 생각한 스터디원의 풀이이다.
가장 초기 풀이. (안쪽부터 시작한 풀이)
'[]' 와 '()'가 있는 곳을 숫자로 바꾼 뒤, 숫자의 좌우를 살펴 괄호로 온전하면 계산하는 식으로 진행했다.
--> 문제 : 완전한 괄호 형식을 구별하기도 어렵고 숫자 계산도 어렵고.. 리스트 중간 중간에 빼고 넣어야해서 안됬다.
----> 절대 안쪽에서 시작하는 풀이는 프로그래밍에서 하지 않는게 맞다.
두번째 풀이. (앞에서부터 시작한 풀이)
리스트를 만든 후, 열린 괄호는 계속 넣고 닫힌게 나오면 지우고, 숫자는 다른 리스트에 보관하는 식으로 진행했다.
완전한 괄호 형식인지 아닌지에 구분을 하면서 숫자를 계산하는데에 있어 조건이 너무 복잡해졌다.
아래는 완전한 괄호 형식인지 먼저 구분하고 그 후에 계산을 하는 식으로 해 두번째 풀이의 문제를 해결한 것 같다.
그래도 백지부터 온전히 내 키보드로 꾸린 배낀듯 배끼지 않은 풀이이다.
import sys
input = sys.stdin.readline
word = input()
# 1번. 완벽한 괄호인가 아닌가?
def isperfect(word):
word_list = []
for i in word:
# 맨 처음에 닫힌 괄호가 나오면 False!
if len(word_list) == 0 and (i == ']' or i == ')'):
return False
# 열린 괄호들은 무조건 넣어버리자. 대신 순.서.대.로
elif i == '(' or i == '[':
word_list.append(i)
# 닫힌 괄호가 나오고 순서 리스트 끝이 같은 모양이면 없애버리기
elif i == ')' and word_list[-1] == '(':
word_list.pop()
elif i == ']' and word_list[-1] == '[':
word_list.pop()
# 다했는데 남아있다? 대칭되지 않는다. 아마 남은건 열린 괄호일 것이다.
if len(word_list) > 0:
return False
# 이걸 다했으면 완벽한 괄호가 된다.
return True
# 2번. 완벽한 괄호 형식이니까 더하고 곱하고 해보자.
def calculate(word):
sum_list = []
for i in word:
# 같은 방법으로 열린 괄호는 다 넣어주고
if i == '(' or i == '[':
sum_list.append(i)
# 닫힌 괄호인데 마지막이 괄호이면 숫자를 넣어준다.
elif i == ')' and sum_list[-1] == '(':
sum_list.pop()
sum_list.append(2)
# 닫힌 괄호인데 리스트 마지막이 숫자이면 그 숫자이전을 확인하여
# 열린 괄호를 찾을때까지 더해준다.(완벽한 형식이기 때문에 논리가 맞는다)
elif i == ')' and sum_list[-1] > 0:
part_sum = 0
for j in range(len(sum_list)-1, -1, -1):
if type(sum_list[j]) == int:
part_sum += sum_list[j]
sum_list.pop()
# 짝이 맞는 괄호를 만나면 반복을 종료한다.
elif sum_list[j] == '(':
sum_list.pop()
break
# 더한 숫자 값에 *2를 해 다시 넣어준다.
sum_list.append(part_sum * 2)
# 다른 괄호의 경우.
elif i == ']' and sum_list[-1] == '[':
sum_list.pop()
sum_list.append(3)
elif i == ']' and sum_list[-1] > 0:
part_sum = 0
for j in range(len(sum_list)-1, -1, -1):
if type(sum_list[j]) == int:
part_sum += sum_list[j]
sum_list.pop()
elif sum_list[j] == '[':
sum_list.pop()
break
sum_list.append(part_sum * 3)
return sum_list
# 정의된 함수를 이용해 완벽한지 여부 파악 후, 더하기 함수로 반환했다.
if isperfect(word):
print(sum(calculate(word)))
else:
print(0)
'백준_알고리즘' 카테고리의 다른 글
[백준] 5567. 구현_결혼식 - Python (0) | 2021.02.10 |
---|---|
[백준] 11286. 구현_절댓값 힙- Python (0) | 2021.02.08 |
[백준] 1260. 너비우선탐색_DFS와 BFS - Python (0) | 2021.02.04 |
[백준] 14891. 구현_톱니바퀴 - Python (0) | 2021.02.02 |
[백준] 1475. 구현_방번호 - Python (0) | 2021.01.30 |