[JAVA] BOJ 1541 잃어버린 괄호

출처 : 백준

숫자와 +, - 연산자가 주어졌을 때 괄호를 넣어서 최솟값을 만드는 문제이다. 그리디 알고리즘은 인간의 두뇌와 정말 비슷한 알고리즘을 가진 것 같다. 이 문제를 봤을 때 사람은 당연히 - 뒤에 오는 숫자는 커야 하고 그렇기 때문에 - 뒤에 오는 숫자의 값을 크게 하기 위해선 +이면 괄호를 쳐주고 -이면 괄호를 치지 않고 진행할 것이다. 따라서 필자는 주어진 입력값을 -로 분리한 후 +로 분리하는 과정을 거쳤다. 무슨 말인가 하면,

 

55-50+40의 문자열이 주어졌을 때 -로 split("-")을 하게 되면 55와 50+40 이 남는다. 다른 예로 125-50-30+20 이 주어지면 125, 50, 30 + 20 이 남는다. 이때 나누어진 수대로 반복문을 돌며 해당 요소를 다시 +로 split("+") 한다. 이때 +로 split 한 것의 길이가 2 이상인 경우 해당 요소들은 더해준다.

 

55, 50+40 를 예로 들면 55는 +로 split을 해도 길이가 1이기 때문에 sum -= 55를 해준다. *첫 번째 숫자는 예외로 더해주어야 하기 때문에 사실상 sum+= 55이다. 

두 번재로 50+40을 split("+") 하면 길이가 2 이상이기 때문에 이때 각 요소들은 더해주고 그 더한 값을 sum에서 빼준다.

 

125,50,30+20을 예로 들면, 125는 +로 split을 해도 길이가 1이기 때문에 빼줘야 하지만 첫 번째 숫자이기 때문에 더해준다. sum=125

50은 +로 split해도 길이가 1이기 때문에 빼준다. sum = 75

30+20은 +로 split하면 길이가 2이기 때문에 각 요소의 합을 빼준다. sum = 25

이를 코드로 구현하면 다음과 같다.

 

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		String s = st.nextToken();
		int sum=0;
		for(int i=0; i<s.split("-").length;i++) {
			if(s.split("-")[i].split("\\+").length>=2) {
				int num=0;
				for(int j=0; j<s.split("-")[i].split("\\+").length;j++) {
					num+= Integer.parseInt(s.split("-")[i].split("\\+")[j]);
				}
				if(i==0) sum+= num;
				else sum-=num;
			}else {
				if(i==0) sum+= Integer.parseInt(s.split("-")[i]);
				else sum-= Integer.parseInt(s.split("-")[i]);
			}
		}
		System.out.println(sum);
	}

}