Baekjoon_1541_잃어버린 괄호

문제 설명

• +, -, 숫자로 이루어진 식이 주어진다.
• '괄호를 적절히 쳐서' => '연산 순서를 적절히 선택해서'

=> 이 식의 값을 최소로 만들어 출력

 

 

문제 풀이

*와 / 가 없기 때문에 비교적 단순한 문제였다.

 

식의 결과가 최소가 되려면 - 연산을 수행하는 수가 최대가 되어야 한다.

 

이를 위해 처음에는 - 뒤의 + 연산을 모두 수행한 후 계산하면 될 것이라 추측했다.

 

하지만 이렇게 연산하면 - 앞의 + 들은 남아있게 된다. 이 + 들은 연산을 먼저하든 나중에하든 남은 - 를 연산하는 과정에서 결과값을 최소화하는데 도움을 주지 않기 때문에, 결과적으로 모든 + 를 연산한 후 남은 - 를 연산하도록 구현했다.

 

따라서 deque에 숫자, queue에 연산기호를 넣고, + 연산기호가 사용되는 수들을 먼저 연산했다.

 

이렇게 남은 수 중 맨 앞의 수를 제외한 나머지는 전부 - 연산을 수행하므로 최소값을 구할 수 있다.

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _1541_잃어버린괄호 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		char[] chars = in.readLine().toCharArray();
		Deque<Integer> numbers = new ArrayDeque<>();
		Queue<Character> signs = new LinkedList<>();
		int idx = 0;
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i<chars.length;++i) {
			if(chars[i] >= '0' && chars[i]<='9') {	//숫자일 때
				sb.append(chars[i]);
			}else {	//기호일 때
				numbers.add(Integer.parseInt(sb.toString()));
				sb.setLength(0);
				signs.add(chars[i]);
			}
		}
		numbers.add(Integer.parseInt(sb.toString()));	//마지막 수 넣기
		numbers.add(numbers.pop());	//맨 앞에 있는 수 맨 뒤로 보내기
		while(!signs.isEmpty()) {	// + 먼저 연산
			char sign = signs.poll();
			if(sign == '+') {
				int num1 = numbers.pollFirst();
				int num2 = numbers.pollLast();
				numbers.add(num1+num2);
			}else {
				numbers.add(numbers.pop());	//맨 앞에 있는 수 맨 뒤로 보내기
			}
		}
		int answer = numbers.pop();
		while(!numbers.isEmpty()) {	//남은 - 연산
			answer -= numbers.pop();
		}
		System.out.println(answer);
	}
}