은학의 코딩 일기장
[백준] 2504 괄호의 값 - 파이썬 본문
문제
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 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
풀이법
전형적인 스택 문제이다.
먼저 입력 array값을 리스트에 담아두고, 사용할 stack, 정답값을 저장할 answer, 괄호 곱하기에 사용할 tmp 변수를 3개 만들어둔다.
괄호가 "(" 이거나 "[" 일 떄는 스택에 집어넣는다. 그 후 괄호끼리 곱하는걸 생각하여 tmp에 정해진 수만큼 곱해준다( (는 *2 [는 3)
괄호가 닫혔을 때가 중요한데, 스택이 비어있거나 스택 맨 위에 값이 현재 괄호 값과 매칭이 안되면
[ ex) ( ] [ ) 이러면 ] 잘못된 것이므로 answer값을 0으로 해둔다.
괄호가 옳게 매칭되고 바로 앞의 괄호와 일치할 경우에는 괄호끼리 더해준다. (이때 tmp에 저장된 값을 더해주므로 부분적으로 곱하기가 되게 된다.)
곱하기 과정이 좀 헷갈렸는데, 우리가 실제로 하는 전체를 더한 후 한꺼번에 곱하는 방식이 아닌 하나하나씩 부분적으로 곱한 후 더하는 방식이였다.
그렇기 때문에 stack에서 값을 빼올 때 마다 tmp값을 나누어줌으로써 중복되는 곱셈을 막아야한다. (여기가 많이 헷갈림)
마지막으로 stack이 True면 괄호 값의 매칭이 잘못된 것이므로 0을 반환하고 그게 아니라면 옳게 매칭된것이므로 더한 answer값을 출력하면 된다!
'알고리즘' 카테고리의 다른 글
[백준] 14719 빗물 - 파이썬 (0) | 2023.03.21 |
---|---|
[알고리즘] 정렬 (0) | 2023.02.21 |
[알고리즘] 완전탐색 (0) | 2023.02.03 |
[알고리즘] BFS (0) | 2023.01.27 |
[알고리즘] DFS (0) | 2023.01.24 |