[백준 / BOJ] 19591 독특한 계산기

문제

출처 : www.acmicpc.net/problem/19591

19591번: 독특한 계산기

수식이 주어졌을때, 계산을 하는 문제다.

계산을 할때 규칙이 있는데,

가장 앞, 혹은 가장뒤에있는 것만 계산할수있다.

 

이때, 곱하기 나누기를 더하기 빼기보다 먼저 계산하고, 수식 우선순위가 같다면 계산결과가 큰것부터 계산한다.

 

풀이

문제에서 하란대로만 구현하면 풀리는문제다.

 

deq자료구조를 이용했다.

 

숫자을 저장하는 deq, 연산자를 저장하는 deq을 각각 만들고, 따로따로 저장해줬다.

 

예제인 

3*2+5-5+7

의 경우

 

num(숫자) = <3, 2, 5, 5, 7> 이 저장되어있을거고,

oper(연산자) = <*, +, -, +>가 저장되어있다.

 

이제, num의 사이즈가 1이될때까지 (oper의 사이즈가 0이 될때까지) 반복을 해준다.

 

num의 앞,뒤 에서 각각 2개를 빼고 연산자의 앞뒤에서 1개를 뺀후, 문제가 시키는대로 계산을하고 결과를 다시 선택한쪽(앞,뒤)에 넣어준다.

앞과 뒤중 선택받지못한쪽은 다시 num과 oper에 그대로 넣어줘야한다는걸 빼먹지말자. 

 

이때, 숫자의 갯수는 항상 (연산자의갯수 * 2 - 1)이라서 이렇게 해도 반례가 없을거라 생각했다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/19591%20%EB%8F%85%ED%8A%B9%ED%95%9C%20%EA%B3%84%EC%82%B0%EA%B8%B0/main.cpp

devxb/JJUNalgo