알고리즘/BOJ

백준 16638번 괄호 추가하기 2

꾸준함. 2020. 5. 24. 16:50

문제 링크입니다: https://www.acmicpc.net/problem/16638

 

16638번: 괄호 추가하기 2

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가

www.acmicpc.net

백준 16637번 괄호 추가하기(https://jaimemin.tistory.com/1454) 와는 다르게 연산자 우선순위가 다른 문제였습니다.

하지만 여전히 중첩괄호는 허용하지 않다보니 수월하게 풀 수 있는 문제였습니다.

아이디어는 자료구조 시간에 배운 후위연산식 만드는 과정과 계산하는 방법에서 얻었으며

이에 대한 내용은 아래 링크를 참고하시면 됩니다!

https://jaimemin.tistory.com/158

 

C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 후위표기법 예제

[중위표기법 -> 후위표기법 예제] /* Write the poostfix form of the following expressions: 다음 식들을 후위표기법으로 표기하라 */ a) A*B*C -> ABC** b) -A+B-C+D -> -AB+-CD+ c) A*-B+C -> A-B*C+ d) (A+B)..

jaimemin.tistory.com

 

알고리즘은 아래와 같습니다.

1. 우선순위를 설정하는데 왼쪽 괄호를 제일 높게, *를 그 다음, 그리고 +와 -는 제일 낮게 부여합니다.

2. func 함수를 호출하고 [idx, N) 범위 내 반복문을 돌립니다.

2.1 범위 내 피연산자 2개와 연산자 1개가 있을 수 없어 괄호로 묶을 수 없을 경우 별 다른 조치 없이 다음 인덱스에 대해 재귀함수를 호출합니다.

2.2 범위 내 피연산자 2개와 연산자 1개가 있고 괄호로 묶을 수 있을 경우 ([i 번째 인덱스] 연산자 [(i + 2) 번째 인덱스]) 와 같이 묶고 재귀함수를 호출합니다.

3. 문자열 s의 인덱스 범위를 벗어났다면 괄호를 다 묶었다고 가정하고 후위연산식 계산을 시작합니다.

3.1 현재까지 구한 최대값과 비교하여 최대값을 갱신해줍니다.

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

 

반응형

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

백준 16639번 괄호 추가하기 3  (2) 2020.05.26
백준 1408번 24  (0) 2020.05.26
백준 16637번 괄호 추가하기  (6) 2020.05.24
백준 1019번 책 페이지  (0) 2020.05.22
백준 13904번 과제  (0) 2020.05.21