백준 16638번 괄호 추가하기 2

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

16638번: 괄호 추가하기 2

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

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

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

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

https://jaimemin.tistory.com/158

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

 

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

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

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

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

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

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

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

 

 

개발환경:Visual Studio 2017

 

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