[백준 알고리즘] 2504번: 괄호의 값 (Python / 파이썬)

2024. 1. 18. 05:37·알고리즘/백준
문제 접근

쉬운 문제인 줄 알았는데 시간이 많이 걸렸다.

올바른 괄호 체크는 ], )가 들어올 때만 체크해주면 된다.

 

숫자 계산이 헷갈리는데, 곱연산에 (,[ 왼쪽 괄호를 사용하고

합연산에 ),] 오른쪽 괄호를 사용한다.

이를 위해 temp와 answer 두 가지 변수를 선언했다.

 

(()[[]])

이 예제를 보고 설명해보면,

이는 2 * ( 2 + 3 * 3 ) = 22 로 나타낼 수 있다.

왼쪽 괄호가 들어올 때 1로 선언된 temp에 2 또는 3을 곱해준다.

그리고 (), []와 같이 바로 닫힐 때

answer에 temp를 더해준다.

 

이때 바로 닫히는 (), []와 같은 형태에서 합연산을 해주는 이유는

그것이 가장 깊은 괄호이기 때문이다.

(), []의 형태가 등장할때까지 스택에는 곱해야 하는 (, [가 들어와 있다.

따라 그 곱연산이 적용된 temp를 answer에다가 더해주면 해당 부분의 연산은 끝난 것이다.

이때 해당 부분을 Pop하고 ()로 닫혔다면 temp를 2로 나눠주고, []로 닫혔다면 temp를 3으로 나눠준다.

(()[[]])

그러나 이 예시에서 ( ( ) -> temp = 2 * 2 = 4 가 되는데

다음 [[]] 부분에서도 temp는 2로 적용되어야 하므로 ()로 닫힐 때 temp를 2로 나누어준다. 

[[]]에서도 temp에 3*3 [[ 연산을 해주고 []로 바로 닫힐 때 합연산을 해주고 ]] -> 나누기 9 해준다.

그러면 다시 temp는 2가 되고 마지막 바깥쪽 )를 만나 다시 2로 나누어져 1로 원상복귀한다.

 

정답 코드
# 2504번: 괄호의 값

import sys

str = sys.stdin.readline().rstrip()


def main():
    stack = []
    temp = 1
    answer = 0

    for i in range(len(str)):
        if str[i] == '(':
            temp *= 2
            stack.append(str[i])
        elif str[i] == '[':
            temp *= 3
            stack.append(str[i])
        elif str[i] == ')':
            if not stack or stack[-1] == '[':
                return 0
            if str[i-1] == '(':
                answer += temp
            stack.pop()
            temp //= 2
        else: # str[i] == ']'
            if not stack or stack[-1] == '(':
                return 0
            if str[i - 1] == '[':
                answer += temp
            stack.pop()
            temp //= 3
    if stack:
        return 0
    return answer


print(main())

 

2504번: 괄호의 값

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X

www.acmicpc.net

 

저작자표시 (새창열림)

'알고리즘 > 백준' 카테고리의 다른 글

[백준 알고리즘] 1012번: 유기농 배추 (Python / 파이썬)  (2) 2024.01.19
[백준 알고리즘] 7576번: 토마토 (Python / 파이썬)  (0) 2024.01.19
[백준 알고리즘] 10799번: 쇠막대기 (Python / 파이썬)  (2) 2024.01.18
[백준 알고리즘] 5430번: AC ( Python / 파이썬 )  (2) 2024.01.15
[백준 알고리즘] 1021번: 회전하는 큐 (Python / 파이썬)  (0) 2024.01.14
'알고리즘/백준' 카테고리의 다른 글
  • [백준 알고리즘] 1012번: 유기농 배추 (Python / 파이썬)
  • [백준 알고리즘] 7576번: 토마토 (Python / 파이썬)
  • [백준 알고리즘] 10799번: 쇠막대기 (Python / 파이썬)
  • [백준 알고리즘] 5430번: AC ( Python / 파이썬 )
gyujh
gyujh
개발 공부 블로그
  • gyujh
    규
    gyujh
  • 전체
    오늘
    어제
    • 분류 전체보기 (86)
      • Backend&DB (3)
      • CS (5)
        • 컴퓨터구조 (1)
        • 소프트웨어공학 (4)
      • JavaScript (2)
      • Git (2)
      • 알고리즘 (73)
        • 개념 (3)
        • 백준 (70)
      • Projects (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    너비우선탐색
    답안
    풀이
    정답
    BOJ
    숏코딩
    구현
    스택
    딕셔너리
    런타임
    시간초과
    프로그래머스
    문자열
    답
    algorithm
    백준
    알고리즘
    에러
    재귀
    정렬
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.1
gyujh
[백준 알고리즘] 2504번: 괄호의 값 (Python / 파이썬)
상단으로

티스토리툴바