백준 1541번 <잃어버린 괄호>

백준 알고리즘 1541번

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

---

1541번

양수와 +, -, 괄호를 가지고 식을 만든 후 괄호를 모두 지웠다. 이 식에 괄호를 적절히 쳐서 이 식의 값을 최소로 만들자.

 

입력으로 첫 줄에 식이 주어진다.

식은 0~9, +, -만으로 이루어져있고, 가장 처음과 마지막 문자는 숫자이다.

연속해서 2개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없으며 숫자는 0으로 시작할 수 있다.

 

출력으로 주어진 식에 괄호를 적절히 쳤을 때, 값이 최소가 되는 값을 출력하면 된다.

---

문제 해결

이 문제의 식에서 사용되는 연산자는 +와 - 두 개 뿐이기 때문에 생각보다 어렵지 않다.

 

식의 결과값을 최소로 만들어야하기때문에 연산자인 +와 -의 경우 2가지로 나눠서 생각해볼 수 있다.

A+B의 경우 A와 B가 작아야 결과값이 작을 수 있다.

A-B의 경우 B의 값이 커야 결과값이 작을 수 있다.

그렇기 때문에 -의 경우를 신경써주면 된다.

 

만약 연산자가 -라면 뒤의 연산자를 보고 +면 계속 더해주고 -를 해야 한다. 이때 당연하게도 연산자가 있을 경우에만 해야 한다.

그래야 A-B에서 B가 커지니까.

 

*수가 0부터 시작할 수 있다는 것은 String으로 받아서 Integer.parseInt()를 사용해서 그냥 숫자로 만들어주면 된다.

---

코드

package bj1541;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();

		int len = input.length();
		String temp = "";

		Queue<Integer> number = new LinkedList<>();
		Queue<String> operator = new LinkedList<>();

		for (int i = 0; i < len; i++) {
			if (input.charAt(i) == '-') {
				number.add(Integer.parseInt(temp));
				temp = "";
				operator.add("-");
			} else if (input.charAt(i) == '+') {
				number.add(Integer.parseInt(temp));
				temp = "";
				operator.add("+");
			} else {
				temp += input.charAt(i);
			}
		}
		number.add(Integer.parseInt(temp));
		len = operator.size();
		int ans = number.poll();
		int operand = 0;
		while(!operator.isEmpty()) {
			operand += number.poll();
			String op = operator.poll();
			if(op.equals("+")) {
				ans += operand;
				operand = 0;
			}else if (op.equals("-")) {
				while(!operator.isEmpty()) {
					String op2 = operator.peek();
					if(op2.equals("+")) {
						operator.poll();
						operand += number.poll();
					}else if(op2.equals("-")) {
						break;
					}
				}
				ans -= operand;
				operand = 0;
			}
			
		}
		System.out.println(ans);

	}

}

코드 ( 22.08.23 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	// 가장 최소값 만들기 -> 연산자는 -, + 뿐이니까 A-B에서 B를 크게 만들면 된다.
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		String[] num = input.split("[+|-]");

		char[] op = new char[num.length - 1];
		for (int i = 0, idx = 0; i < input.length(); i++) {
			if (input.charAt(i) == '+' || input.charAt(i) == '-') {
				op[idx] = input.charAt(i);
				idx++;
			}
		}
		int a = Integer.parseInt(num[0]);
		for (int i = 0; i < num.length - 1; i++) {
			int b = Integer.parseInt(num[i + 1]);
			if (op[i] == '+') {
				a += b;
			} else if (op[i] == '-') {
				i++;
				while (i < op.length) {
					if (op[i] == '+') {
						b += Integer.parseInt(num[i + 1]);
					} else if (op[i] == '-') {
						i--;
						break;
					}
					i++;
				}
				a = a - b;
			}
		}
		System.out.println(a);

	}

}

---

결과

---