[백준] 1541. 잃어버린 괄호 (자바 JAVA)

[ 문제 ]  [백준] 1541. 잃어버린 괄호 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

---

# 접근 방법 및 풀이 

 

• 그리디 + 문자열 문제다.
• 처음에 이거보고 바로 아이디어가 안 떠올라서 화가났다. 그리디 문제를 더 풀어봐야할 것 같다.
• 문제는 적절히 괄호를 쳐서 식의 값을 최소로 만들어야 한다.
• 최소값이 나오기 위해선 - 기준으로 식을 나누고, +가 있는 식들을 다 계산해서 최종적으로 빼주면 된다.
• 예제 1번처럼, 55 - 50 + 40 일 경우, - 기준으로 55와 50 + 40 으로 식을 나누고, +가 있는 50+40을 계산한 후 
• 55 - 90 을 해주면 -35가 나온다. 
• StringTokenizer을 2개 사용해 하나는 - 기준으로 문자열을 나누고, 또 다른 하나는 + 기준으로 문자열을 나눠서 풀었다.
• 자세한건 코드참조

# 주의할 점 

 

• 식에서 최솟값을 만들 수 있는 방법 떠올려보기

 

JAVA 코드

package Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class bj1541_잃어버린괄호 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), "-");
		List<Integer> list = new ArrayList<>();
		while(st.hasMoreTokens()) {
			String s = st.nextToken();
			StringTokenizer st2 = new StringTokenizer(s, "+");
			int sum = 0;
			while(st2.hasMoreTokens()) {
				sum += Integer.parseInt(st2.nextToken());
			}
			list.add(sum);
		}
		int ans = list.get(0);
		for (int i = 1; i < list.size(); i++) {
			ans -= list.get(i);
		}
		System.out.println(ans);
	}
}

 

 

 

REVIEW

그리디 문제는 아이디어를 떠올리면 쉬워보이는데, 그 아이디어를 떠올리기가 쉽지 않다.

알고리즘 문제를 많이 풀어봤다고 잘 하고 있다고 생각했는데.. 나는 아직 한 참 멀었다!