[백준] 1541번 : 잃어버린 괄호

---

풀이 방법

알고리즘 분류는 그리디 알고리즘인데, 내가 푼 방법은 다르게 풀었었다.
55-50+40 이라는 입력이 들어오면
55-(50+40) 이렇게 묶어서 최소 값인 -35가 되는 문제였다.

내가 푼 풀이는 -기호를 만나면 뒤에 모든 숫자의 부호가 -가 된다는 법칙을 발견해서 해결했다.

만약 5-3+4-2+5-6 이런식으로 기호가 섞여있어도
5-(3+4)-(2+5)-6 이렇게 결국 다 -로 변화는 걸 확인할 수 있다.

이번에 알게된 점은 문자열에서 숫자와 기호를 StringTokenizer로 분리하는 방법이였다.

// 입력, 분리할 문자, 분리할 문자도 token화 할건지
StringTokenizer st = new StringTokenizer(br.readLine(),"-+", true);

코드

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


public class Main {

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

        StringTokenizer st = new StringTokenizer(br.readLine(),"-+", true);

        Queue<Integer> nums = new ArrayDeque<>();
        Queue<String> patterns = new ArrayDeque<>();

        int result = 0;

        while (st.hasMoreTokens()) {
            String token = st.nextToken();
            if(isNumber(token)) {
                nums.add(Integer.valueOf(token));
            } else {
                patterns.add(token);
            }
        }

        while(!patterns.isEmpty()) {
            result += nums.remove();
            if(patterns.remove().equals("-")){
                while(!nums.isEmpty()){
                    result -= nums.remove();
                }
                break;
            }
        }
        if(!nums.isEmpty()){
            result += nums.remove();
        }
        System.out.println(result);
    }

    private static boolean isNumber(String token) {
        try {
            Integer.parseInt(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}