99클럽 코테 스터디 30일차 TIL / 잃어버린괄호(백준)

오늘의 학습 키워드

   - 알고리즘

   - 그리디

공부한 내용 본인의 언어로 정리하기

https://www.acmicpc.net/problem/1541

그리디 알고리즘을 이용한 문제를 풀었다. 아이디어가 가장 어려웠지만 아이디어를 떠올린 이후로는 풀 만 했다.

 

풀이 과정은 다음과 같다.

1. '-'를 기준으로 문자열 파싱

2. 파싱된 문자열들을 '+'를 기준으로 파싱 후 모두 합산

2 - 1. 그러면 모든 덧셈 연산은 완료된 상태

ex) 10 + 20 - 30 + 40 -> 30 - 70

3. 위 상태에서 첫 번째 숫자를 제외한 모든 숫자들을 빼주면 최소값

 

풀이는 다음과 같다.

import java.util.*;
import java.io.*;


public class Main {

    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();

    public static void main(String args[])throws IOException {

        String[] splitMinus = br.readLine().split("-");

        int splitMinusLen = splitMinus.length;
        String[][] splitPlus = new String[splitMinusLen][];
        int[] sumSplitMinus = new int[splitMinusLen];

        for (int i = 0; i < splitMinusLen; i++) {
            splitPlus[i] = splitMinus[i].split("\\+");
            for (int j = 0; j < splitPlus[i].length; j++) {
                sumSplitMinus[i] += Integer.parseInt(splitPlus[i][j]);
            }
        }

        int minSum = sumSplitMinus[0];

        for (int i = 0; i < splitMinusLen; i++) {
            minSum -= sumSplitMinus[i];
        }


        System.out.println(minSum);
    }
}