[백준 1541]https://www.acmicpc.net/problem/번호
문제 조건
양수와 +, -로 이루어진 식에서 괄호를 적절히 쳐서 식의 결과값을 최소로 만들어야 한다.
문제 입력
첫째 줄에 식이 주어진다.
식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.
연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다.
수는 0으로 시작할 수 있다.
입력으로 주어지는 식의 길이는 50보다 작거나 같다.
문제 풀기 전 설계
한 줄로 들어오는 식에서 수와 연산자를 하나씩 분리해서 큐에 담고 큐에서 값을 하나씩 뽑아가면서 식의 값을 정하면 될 것이다.
'-' 연산자가 나오기 전에는 수를 전부 더하고, '-'가 한 번이라도 나왔다면 괄호를 통해 뒤에 나오는 수는 전부 뺄 수 있다. -> 연산자를 식별해서 '-'가 언제 나오는지 알면 된다.
문제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Queue<String> q = new LinkedList<>(); // 수와 연산자를 하나씩 담을 큐
StringTokenizer st = new StringTokenizer(br.readLine(),"+", true); // 입력받은 문자열을 "+"를 기준으로 토큰화한다.
while (st.hasMoreTokens()) {
// 새 StringTokenizer를 생성해 "+"를 기준으로 나뉜 토큰을 "-" 기준으로 한 번 더 나눈다. 이러면 숫자, "-", "+"로 나뉜다.
StringTokenizer st2 = new StringTokenizer(st.nextToken(), "-", true);
while (st2.hasMoreTokens()) { // 나뉜 토큰을 큐에 삽입한다.
q.offer(st2.nextToken());
}
}
int repeat = q.size();
int sum = 0; // 출력할 값
boolean isMinus = false; // "-" 연산이 나왔는지 체크하는 변수
for (int i = 0; i < repeat; i++) {
if (i % 2 == 0) { // 인덱스가 0부터 시작하므로 짝수 번 인덱스에는 숫자가 나온다.
int num = Integer.parseInt(q.remove()); // 입력받은 수
if (isMinus) sum -= num; // 만약 한 번이라도 "-"가 나왔다면 앞의 합산한 결과에 -num
else sum += num; // 그렇지 않다면 앞의 합산한 결과에 +num
}
else { // 홀수 번 인덱스에는 "+" 또는 "-"가 나온다.
char plusMinus = q.remove().charAt(0);
if (plusMinus == '-') isMinus = true; // "-" 연산이 나오면 isMinus를 true로 바꾼다.
}
}
System.out.println(sum);
}
}문제 풀이
연산이 "+"와 "-" 뿐이기 때문에 값이 최소가 되려면 "-" 연산을 최대로 해야 한다.
괄호를 마음대로 사용할 수 있기 때문에 "-" 연산자가 하나라도 나오면 그 뒤에 나오는 모든 수는 "-" 연산을 할 수 있다.
50+30-20+10+40+20 => 50+30-(20+10+40+20)
30-20+50-10+40-20 => 30-(20+50)-(10+40)-20
이렇게 "-" 연산 뒤의 "+" 연산은 전부 "-" 연산으로 바꿀 수 있다.
그렇기에 "-" 연산이 나오기 전까지는 이전 결과값에 현재 수를 더해주고, "-" 연산이 나온 후에는 이전 결과값에서 현재 수를 빼는 것이 최솟값이 된다.
Review
직접 예제 식을 몇 개 세워보니 쉽게 풀리는 문제였다. 이번 문제에서 가장 중요했던 부분은 "문자열을 어떻게 나누어 처리할 것인지" 였는데 StringTokenizer의 구획문자(delimiter)라는 요소를 사용하여 해결했다. 이전까지는 단순히 공백문자로 나뉜 입력이 많아서 구획문자를 쓸 일이 없었는데, 구획문자를 활용하여 문제를 풀 기회가 생겨 좋았다.
