문제 링크입니다: https://www.acmicpc.net/problem/16638
백준 16637번 괄호 추가하기(https://jaimemin.tistory.com/1454) 와는 다르게 연산자 우선순위가 다른 문제였습니다.
하지만 여전히 중첩괄호는 허용하지 않다보니 수월하게 풀 수 있는 문제였습니다.
아이디어는 자료구조 시간에 배운 후위연산식 만드는 과정과 계산하는 방법에서 얻었으며
이에 대한 내용은 아래 링크를 참고하시면 됩니다!
https://jaimemin.tistory.com/158
알고리즘은 아래와 같습니다.
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 |