[Algorithm] Greedy 잃어버린 괄호(백준) - 에이젠

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

1541번: 잃어버린 괄호

 

'공략

 

알고리즘 중급 1/3 의 그리디 연습 문제입니다.

+ - 연산만으로 이루어진 식에 적절히 괄호를 사용하여 최솟값을 출력하는 것이 목표입니다.

가장 큰 수를 뺄셈해주면 최솟값이 나오는 것을 우리는 알고 있죠.

따라서 모든 +연산을 수행하고 마지막에 남은 - 연산을 해주면 답이 나오겠습니다.

 

import java.util.*;

public class Main {

  static Scanner sc = new Scanner(System.in);
  static String str;
  static String[] numArr;
  static ArrayList<Integer> intArr = new ArrayList<>();
  static ArrayList<String> signArr = new ArrayList<>();

  static void input() {

    str = sc.next();
    numArr = str.split("\\+|\\-");
    for (int i = 0; i < numArr.length; i++) {
      intArr.add(Integer.parseInt(numArr[i]));
    }

    intArr.add(0);
    for (int i = 0; i < str.length(); i++) {
      if (str.charAt(i) == '-') {
        signArr.add("-");
      } else if (str.charAt(i) == '+') {
        signArr.add("+");
      }
    }

  }

  static void findAns() {
    // 덧셈 먼저 연산하기
    for (int i = 0; i < signArr.size(); i++) {
      if (signArr.get(i) == "+") {
        int a = intArr.get(i);
        int b = intArr.get(i + 1);
        int result = calc(a, b, "+");
        intArr.set(i, result);
        if (intArr.size() > i + 1) {
          intArr.remove(i + 1);
        }
        signArr.remove(i);
        i--;
      }
    }

    // 나머지 뺄셈 연산하기

    while (!signArr.isEmpty()) { // 모든 뺄셈을 연산할때까지 반복
      String sign = signArr.get(0);
      int firstNum = intArr.get(0);
      int secondNum = intArr.get(1);
      int result = calc(firstNum, secondNum, "-");
      intArr.remove(1);
      intArr.set(0, result);
      signArr.remove(0);
    }
    int ans = intArr.get(0);
    System.out.println(ans);
  }

  static int calc(int a, int b, String sign) {
    if (sign == "+") {
      return a + b;

    } else if (sign == "-") {
      return a - b;

    }
    return a + b;

  }

  public static void main(String[] args) {

    input();
    findAns();
  }
}