[백준] 1541 잃어버린 괄호

1. 문제 설명 📌

문제링크

2. 접근 방식 🗃️

KEY WORD: GREEDY ALGORITHM
Greedy Algorithm은 매 선택의 순간마다 당시 최선의 선택을 하는 것이 전체 문제에서 봤을 때 최선이라는 가정을 하는 알고리즘이다.

해당 문제는 -를 만난 순간부터 뒤에는 무조건 괄호를 활용해 모든 값을 -로 만들어버리면 된다. 최초 -를 만난 후 뒤의 계산에 +가 오든 -가 오든 적절히 괄호만 치면 모든 값을 -로 만들 수 있다. 예를 들어

25 + 32 - 26 - 27 + 28 - 29 + 30 - 31

25 + 32 - 26 - (27 + 28) - (29 + 30) - 31

처럼 말이다.

3. 코드 소개 🔎

(0) 사전 지식

문제의 입력이 String으로 뭉뚱그려 주어지기 때문에 문자열 자르기에 숙달이 되있어야 한다.
나는 StringTokenizer를 활용했다.

StringTokenizer st = new StringTokenizer("문자열", "문자열 자르는 기준이 되는 문자", 해당 문자를 포함할 것인지 delim);

여기서 두번째 인자에는 ,를 통해 기준 문자를 여러개 설정할 수있고, 3번째 인자를 true로 주면 자르는 기준이 되는 문자도 받을 수 있다. 예를 들어

input: "55-50+40";

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

while(st.hasMoreTokens()){
    System.out.println(st.nexToken());
}

/* 출력
55
-
55
+
40
*/

이렇게 온다. 이를 문제에 활용하여 -가 온 이후로 모든 값을 빼면 된다.

import java.io.*;
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);

        int acc = 0;
        boolean isMinus = false;
        while (st.hasMoreTokens()){
            String now = st.nextToken();
            if(!now.equals("+") && !now.equals("-")){
                if(isMinus) acc -= Math.abs(Integer.parseInt(now));
                else acc += Integer.parseInt(now);
            }
            if(now.equals("-")) isMinus = true;
        }

        System.out.println(acc);
    }
}

4. 배운 것들 🎯

StringTokenizer를 간만에 제대로 다뤄본 거 같다. 덕분에 StringTokenizer의 delim 복수 등록과 delim 포함 여부에 대한 복습을 한 것 같다.