[BOJ] 1541 - 잃어버린 괄호(Java)

문제

괄호를 적절히 쳐서 식의 값을 최소로 만드는 문제

🛠 사용 기술

• StringTokenizer(문자열)
• 그리디 알고리즘

---

Approach 1 ⭕

🔍 접근법

최소값을 만들기 위해서는 최대한 많이 값을 누적해 더해뒀다가 한번에 빼줘야한다. 즉, 뺄셈 기호(-) 이후에는 가능한 모든 수를 괄호로 묶어서 한 번에 빼주는 전략이 필요하다. 이 작업을 위해서 먼저 ‘-’ 기준으로 문자를 분리하고, 이후에 분리된 문자 내에서 ‘+’를 기준으로 값을 누적해 더한 후 전체에서 이를 빼준다.

55 - 50 + 40 
=> 55 - (50 + 40) = -35 (최소값)
=> 55 - 50 + 40 = 45

1. 뺄셈 연산이 시작되는 시점부터는 전부 빼야 하므로 먼저 ‘-’를 기준으로 분리한다.
2. 이후 1번 과정에서 분리된 문자열 내에서 괄호 안의 값들을 모두 더한 후, 한 번에 빼기 위해 각 부분을 ‘+’를 기준으로 더해준다.
3. 첫 번째 덧셈 그룹은 무조건 양수이므로 가장 첫 번째 그룹은 빼지 않고 그대로 세팅해줘야 한다. 이를 위해 Interger.MAX_VALUE를 초기 값에 두고 비교하기 위해 사용한다.

💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        StringTokenizer st = new StringTokenizer(sc.next(), "-");

        int sum = Integer.MAX_VALUE;
        while(st.hasMoreTokens()){
            StringTokenizer temp = new StringTokenizer(st.nextToken(), "+");
            int addition = 0;

            while(temp.hasMoreTokens()){
                addition += Integer.parseInt(temp.nextToken());
            }

            if(sum == Integer.MAX_VALUE){ // 초기값은 빼주지 않고 그대로 세팅
                sum = addition;
            }else{
                sum -= addition;
            }
        }

        System.out.println(sum);
    }
}

---

느낀 점 및 메모 💡

• 그리디 알고리즘의 핵심은 지역 최적 선택이 전체 최적을 보장한다는 점인데, 이 문제는 뺄셈 뒤의 모든 수를 한 번에 빼는 것이 최선이라는 점에서 직관적이다.
• StringTokenizer는 공백 없이 여러 구분자를 기준으로 문자열을 빠르게 분리할 수 있어, 입력 처리 시 split()보다 유용할 때가 많다. 주로 사용하는 함수는 다음과 같다. 

hasMoreTokens, countTokens, nextToken

• hasMoreTokens() 함수는 다음 토큰이 존재하면 true를 리턴하므로 조건문이나 반복문에서 활용할 수 있다. countTokens() 함수는 전체 토큰의 갯수를 리턴한다. nextToken() 함수는 다음 토큰을 리턴한다.