1. 문제 정리
1.1 문제 개요
세준이는 양수와 '+', '-' 연산자 그리고 괄호를 사용해 하나의 식을 만들었습니다.
그러나 나중에 세준이는 식에서 모든 괄호를 지워버렸습니다.
이제 세준이는 원래의 식에 괄호를 적절히 추가하여 최소 결과값을 만들어 내고자 합니다.
즉, 괄호의 배치를 잘 조정하여 식의 계산 결과가 최소가 되는 값을 구하는 문제입니다.
1.2 입력 조건
•
입력 형식: 한 줄로 구성된 수식
•
수식 구성:
◦
0부터 9까지의 숫자
◦
'+', '-' 기호
•
제약 사항:
◦
식의 첫 번째와 마지막 문자는 반드시 숫자이다.
◦
연속해서 두 개 이상의 연산자가 등장하지 않는다.
◦
한 숫자가 5자리를 초과하지 않는다.
◦
숫자는 선행하는 0을 포함할 수 있다.
◦
식의 길이는 최대 50자이다.
•
괄호를 적절히 추가하여 계산했을 때의 최소 결과값을 출력합니다.
1.4 예제
•
예제 1
◦
입력: 55-50+40
◦
출력: 35
•
예제 2
◦
입력: 10+20+30+40
◦
출력: 100
•
예제 3
◦
입력: 00009-00009
◦
출력: 0
2. 코드 설명
2.1 C++ 코드
#include <iostream>
#include <string>
int main()
{
std::string expression;
std::cin >> expression;
int sum = 0;
bool isMinus = false; // 처음 '-'가 나왔는지 여부를 판단하는 플래그
std::string number; // 현재까지 누적된 숫자를 저장하는 문자열
// 식을 한 글자씩 순회하며 처리
for (char c : expression)
{
// 연산자 '+' 또는 '-'를 만났을 때
if (c == '+' || c == '-')
{
// '-' 이후부터 등장하는 숫자는 빼줌
if (isMinus)
{
sum -= std::stoi(number);
}
// 아직 '-'가 나오지 않은 상태이고, 현재 연산자가 '+'인 경우
else if (c == '+')
{
sum += std::stoi(number);
}
// 처음 '-' 연산자가 등장한 경우
else if (c == '-')
{
isMinus = true;
sum += std::stoi(number);
}
number.clear(); // 다음 숫자 입력을 위해 초기화
}
// 현재 문자가 숫자인 경우, number에 누적
else
{
number.push_back(c);
}
}
// 마지막에 남은 숫자 처리
if (isMinus)
{
sum -= std::stoi(number);
}
else
{
sum += std::stoi(number);
}
std::cout << sum;
return 0;
}
C++
복사
2.2 코드 동작 설명
1.
입력 및 변수 초기화
•
expression: 입력받은 수식을 저장하는 문자열입니다.
•
sum: 최종 결과값을 누적할 변수입니다.
•
isMinus: 처음 '-' 연산자가 등장했는지 여부를 나타내는 불리언 변수입니다.
•
number: 현재까지 연속된 숫자를 문자열 형태로 누적하기 위한 변수입니다.
2.
문자열 순회 및 처리
•
식을 한 글자씩 순회하면서,
◦
연산자('+' 또는 '-')를 만났을 때:
▪
현재까지 누적된 문자열 number를 정수로 변환하여 처리합니다.
▪
isMinus 플래그에 따라,
•
이미 '-'가 등장한 경우: 해당 숫자를 빼준다.
•
그렇지 않은 경우,
◦
현재 연산자가 '+'라면 더해준다.
◦
현재 연산자가 '-'라면 첫 번째 '-'로 간주하고, 해당 숫자를 더한 후 isMinus를 true로 설정합니다.
▪
연산자 처리 후, number를 초기화하여 다음 숫자 처리를 준비합니다.
◦
숫자일 경우:
▪
number에 해당 숫자를 계속 누적합니다.
3.
마지막 숫자 처리 및 결과 출력
•
반복문이 종료된 후, 남아있는 number에 대해 같은 조건에 따라 처리합니다.
•
최종적으로 누적된 sum 값을 출력합니다.
3. 알고리즘 설명
3.1 핵심 아이디어 및 전략
•
핵심 아이디어:
입력된 식에서 첫 번째 '-' 이후의 모든 연산은 결과값을 최소화하기 위해 빼야 합니다.
더하기가 많을 수록 결과가 커지기 때문에, 첫 번째 '-'가 등장한 후부터 모든 숫자들을 앞에서 더한 합에서 빼도록 괄호 처리해야 합니다.
•
전략:
1.
첫 번째 '-' 전까지의 숫자들:
•
이 구간에서는 '+'만 있으므로 모든 숫자를 단순히 더합니다.
2.
첫 번째 '-' 이후부터의 숫자들:
•
이때부터 등장하는 모든 숫자는 이전에 더한 숫자들의 합에서 빼줍니다.
3.
이를 위해 식을 한 번 순회하면서,
•
'+'나 '-'가 등장할 때마다 현재까지 누적된 숫자를 정수로 변환하고,
•
isMinus 플래그를 사용하여 해당 숫자를 더할지 빼줄지 결정합니다.
3.2 시간 복잡도 및 공간 복잡도 분석
•
시간 복잡도:
식의 길이를 n이라 할 때, 한 번의 순회(O(n))로 모든 문자를 처리합니다.
•
공간 복잡도:
사용되는 변수들은 몇 개의 정수형, 불리언형, 그리고 문자열 변수 정도이므로, 추가적인 공간 복잡도는 O(1)입니다.