#1541번 : 잃어버린 괄호
문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
예제 입력
55-50+40
예제 출력
-35
풀이
연산 결과값을 최소로 만들기 위해선, 괄호로 어디를 묶어야 하는지가 핵심이었습니다.
결과값이 작은 수가 되려면, 작은 수에서 큰 수를 빼줘야 합니다. 여기서 주목할 점은, '큰 수를 뺀다' 라는 부분입니다.
즉, 피연산자가 큰 수가 되도록 합연산되는 부분을 괄호로 묶어 먼저 계산해주고, 뺄셈을 가장 마지막에 처리해주면 됩니다.
string input;
input = Console.ReadLine();
string[] exMinusBraket = input.Split('-');
먼저 합연산 부분을 괄호로 묶는 처리를 위해, input 문자열을 '-' 를 기준으로 Split('-') 해 나눠줍니다.
Split('-') 한 결과값, 즉 합연산되는 문자열들을 배열에 저장하면 빼기 전 합연산할 준비가 완료되었습니다!
int result = 0;
bool isFirst = true;
···
foreach (string ex in exMinusBraket)
{
int sum = 0;
string[] sumExpression = ex.Split('+');
foreach(string element in sumExpression)
{
sum += int.Parse(element);
}
if(isFirst)
{
result = sum;
isFirst = false;
}
else
{
result -= sum;
}
}
이후 합연산 문자열끼리 묶었던 exMinusBraket 배열에서 foreach() 문으로 문자열을 꺼냅니다.
꺼낸 문자열을 '+' 기호를 기준으로 Split('+') 해주고 배열에 넣은 뒤, 배열의 요소들을 모두 더해주면 괄호로 묶은 합연산은 모두 완료가 되겠죠.
괄호로 묶은 부분의 합연산을 수행한 뒤엔, 순서대로 뺄셈을 진행하면 됩니다.
이 때, 첫 번째로 오는 합연산 결과는 뺄셈의 대상이 되어줘야 하기 때문에, bool 조건으로 체크해서 result 변수에서 값을 빼지 않고 대입해줍니다. 이후의 합연산 결과값들은 result 변수에서 빼주면 됩니다.
C#으로 작성한 전체 코드는 아래와 같습니다.
int result = 0;
bool isFirst = true;
string input;
input = Console.ReadLine();
string[] exMinusBraket = input.Split('-');
foreach (string ex in exMinusBraket)
{
int sum = 0;
string[] sumExpression = ex.Split('+');
foreach(string element in sumExpression)
{
sum += int.Parse(element);
}
if(isFirst)
{
result = sum;
isFirst = false;
}
else
{
result -= sum;
}
}
Console.WriteLine(result);
처음에는 괄호로 묶는게 가능한 모든 케이스를 트리로 만들고, 탐색한 뒤 가장 작은 결과값을 뽑는 건가...? 라는 얼토당토않은 생각을 했었습니다. 천천히 다시 생각해보니 결국 합연산으로 붙은 부분만 괄호로 묶어 큰 수를 만든 뒤, 그 큰 수들을 빼주면 된다는 깨달음을 얻을 수 있었습니다.
첫 깨달음을 얻은 뒤, 괄호로 수식을 묶기 위해서 처음엔 기호와 숫자를 모두 분리하려고 했습니다. 그러다 보니 분할 문자가 사라지는 Split() 메소드는 사용할 수 없었고, Regex.Split() 의 정규 표현식을 사용해봤습니다.
string pattern = @"([+-])";
string[] expression = Regex.Split(input, pattern);
하지만 결국 해야 하는 연산이, 합연산을 먼저 처리한 뒤 뺄셈을 하는 순서여서 단순 Split() 을 통해서 분리만 해줘도 충분하다는 두번째 깨달음을 얻어 코드를 단순화할 수 있었습니다.