[JAVA] BOJ(백준) - 잃어버린 괄호 - 1541번

문제내용

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

1541번: 잃어버린 괄호

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다. 

---

문제 접근 방법

문제에서 주어진 문자열에 괄호를 적절히쳐서 최솟값을 만들기 위해선 어떻게 해야할까 생각을 했다.

그리고 생각보다 간단하게 최솟값을 만들수 있었는데 아래 예를 보자.

 

문제의 예시에서 55-50+40 은 55-(50+40) 을 만들어서 출력값이 -35가 나온다는걸 볼 수 있다.

그렇다면 60-50+40-20+10-30 은 어떻게 괄호를 쳐야하는지 보면 모두 알다시피

60-(50+40)-(20+10)-30 이렇게 쳐야 최솟값이 나오게 된다.

 

이를 잘 살펴보면 주어진 문자열 수를 앞에서부터 계속 더하다가 '-' 가 나온순간부터 뒤의 모든 수는 -를 해주면된다.

즉, 60-50+40-20+10-30 는 60-50-40-20-10-30 이런 모습인거다.

 

위의 예처럼 계산하기 위해

입력받은 문자열을 문자로 나눌때 임시로 저장해놓을 temp 변수,

'-'가 나왔었는지 안나왔었는지 알려줄 sign 변수,

숫자(문자열)와 연산자(문자열)로 묶어서 저장해 놓을 큐를 정의해 풀었다.

 

일단 풀이를 보자.

 

---

풀이

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

public class Main {
	static Queue<String> oper;//숫자와 연산자로 묶어 저장할 큐
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();//문자를 합칠때 사용할꺼.
		
		String a = br.readLine();//입력받는 문자열
		oper = new LinkedList<String>();
		
		//문자열을 나눈 문자를 temp에 임시로 저장 후 oper 큐에 숫자(문자열)과 연산자(문자열)로 저장. 
		char temp;
		for(int i=0; i<a.length(); i++) {
			temp = a.charAt(i);
			if(temp!='+' && temp!='-') {
				sb.append(temp);
			}else {
				oper.add(sb.toString());
				oper.add(String.valueOf(temp));
				//oper에 숫자와 연산자 저장후 sb초기화.
				sb.delete(0, sb.length()); 
			}
		}
		//마지막 숫자는 따로 저장처리.
		//마지막 숫자의 경우 for문에서 else로 안넘어감. 그뒤에 연산자가 없기 때문
		oper.add(sb.toString());
		
		int min = Integer.parseInt(oper.poll());//최솟값
		int sign = 0;//0이면 '-'가 안나왔던거, 1이면 '-'가 나왔던거.
		while(!oper.isEmpty()) {//큐가 빌때까지 계산
			if(!oper.peek().equals("+") && !oper.peek().equals("-")) {
				if(sign == 1) {min -= Integer.parseInt(oper.poll());}
				else {min += Integer.parseInt(oper.poll());}
			}else if(oper.peek().equals("-")) {
				oper.poll();
				sign = 1;
			}else {
				//'+' 일땐 '+' 갖다 버림. 필요없음.
				oper.poll();
			}
		}
		System.out.println(min);
	}
}

 

---

마치며

참고로 다른 블로그를 보면 split과 StringTokenizer를 이용해 풀었는데 좋은 방법이라고 생각하고 나도 다시 풀어볼 생각이다.