[Baekjoon] 1541번: 잃어버린 괄호

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

---

 

문제 해결 과정

착안

주어지는 식에 괄호를 적절히 씌워 결과값이 최소가 되게 하려면, 최대한 뺄셈을 많이 수행하고 큰 숫자를 빼는 것과 같으므로, 뺄셈을 기준으로 식을 나누어 괄호를 씌우는 것과 같다 (또는, 주어진 식에서 덧셈 연산을 뺄셈 연산보다 높은 우선순위로 계산한 다음 왼쪽부터 순차적으로 뺄셈을 수행하는 것과 같다).

 

구현

주어진 식에 대해 덧셈 연산을 우선적으로 진행한 다음, 식의 처음부터 순차적으로 뺄셈을 계산하게 되면 주어진 문자열(계산식)에 대해 반복문을 두 차례 수행해야하기 때문에 비효율적일 수 있다.

 

따라서, 문자열의 오른쪽 마지막부터 왼쪽 방향으로 문자를 검사하여 아래와 같은 동작을 수행하도록 구현하였다.

 

• $i$번째 문자가 '+'인 경우: 각각 왼쪽, 오른쪽 피연산자를 구하여 더한 계산 결과를 문자열에 다시 포함.
• $i$번째 문자가 '-'인 경우: 오른쪽 피연산자와 연산자를 문자열에서 제거하고 숫자를 뺀 결과를 누적하여 저장.

 

최종적으로는 덧셈을 누적하여 하나의 숫자로 합쳐진 문자열을 int 형의 값으로 변환한 값과, 누적된 뺄셈 값을 더하여 출력함으로써 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string Expr;
	cin >> Expr;

	int sum = 0;
	for (int i = (int)Expr.size() - 1; i > 0; i--)
	{
		if (Expr[i] == '-')
		{
			sum -= stoi(Expr.substr(i + 1));
			Expr = Expr.substr(0, i);
		}
		else if (Expr[i] == '+')
		{
			int lhs = i;
			while (lhs--)
			{
				if (lhs > 0)
				{
					if (!(Expr[lhs] >= '0' && Expr[lhs] <= '9'))
					{
						lhs++;
						break;
					}
				}
				else
					break;
			}
			Expr = Expr.substr(0, lhs) + to_string(stoi(Expr.substr(lhs, i - lhs)) + stoi(Expr.substr(i + 1)));
		}
	}
	sum += stoi(Expr);

	cout << sum << "\n";
	return 0;
}

 

실행 결과

 

---

 

문제를 간단하게 해결하기는 했는데 뭔가 더 좋은 풀이방법이 있을 것만 같다...