[BaekJoon] 1541 잃어버린 괄호

1.  문제 링크

2.  문제

요약

• 양수, +, -를 이용하여 식을 만들었는데 여기서 괄호를 모두 지운 후에 괄호를 적절히 쳐서 최소의 수를 만드는 프로그램을 작성합니다.
• 입력: 첫 번째 줄에 식이 주어집니다.
• 출력: 최소의 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public int getMinResult(String expression) {
		StringTokenizer st = new StringTokenizer(expression, "+-");
		ArrayList<Integer> num = new ArrayList<Integer>();
		while(st.hasMoreTokens()) {
			num.add(Integer.parseInt(st.nextToken()));
		}
		ArrayList<String> operator = new ArrayList<String>();
		st = new StringTokenizer(expression, "0123456789");
		while(st.hasMoreTokens()) {
			operator.add(st.nextToken());
		}
		for(int i = 0; i < operator.size(); i++) {
			if(operator.get(i).equals("+")) {
				int temp = num.get(i) + num.get(i + 1);
				num.remove(i);
				num.remove(i);
				num.add(i, temp);
				operator.remove(i);
				i--;
			}
		}
		int result = num.get(0);
		for(int i = 1; i < num.size(); i++) {
			result -= num.get(i);
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String expression = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.getMinResult(expression) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 식은 연산자가 +와 -로만 이루어져 있기 때문에 +로 되어 있는 값들에 괄호를 쳐서 가장 큰 수를 만든 후, 이 수들을 처음부터 순서대로 빼준다면 최소의 수가 나올 것입니다.
• 숫자와 연산자를 각각 분리하여 ArrayList에 넣어준 후, 연산자가 +인 곳에서는 연산자 앞, 뒤의 숫자를 더하고 기존에 들어있던 앞, 뒤 숫자를 지운 후에 더한 수를 그 자리에 넣어줍니다. + 연산자는 이용한 후에 연산자에 대한 ArrayList에서 지워줍니다.
• for문에서 + 연산자를 지운 후에 i를 1 빼주지 않는다면 + 연산자 바로 다음 연산자를 가리키는 것이 아니고 + 연산자를 지웠기 때문에 + 연산자보다 2개 뒤에 있는 연산자를 가리키므로 + 연산자를 지운 후에 1을 빼줍니다.
• 이렇게 + 연산자에 대한 값들을 우선 먼저 계산해준 뒤에 계산된 결과가 들어있는 숫자에 대한 ArrayList에 들어있는 값들을 처음부터 빼기 연산을 진행하면 최소의 수가 나옵니다.