[백준] 잃어버린 괄호(그리디 알고리즘)

---

백준 온라인 저지 11047번 - 잃어버린 괄호

지난 그리디 알고리즘 포스팅에서 공부한 것을 적용하기 위해 또 하나의 그리디 알고리즘 관련 문제를 풀이했다.
문자열로 주어진 수식에서 가장 최소값을 구하려면 어떻게 괄호를 쳐야할까를 고민했을 때 빼기 연산(-)을 진행할 때 최대한 큰 값으로 빼기 연산을 한다면 최소값이 나오지 않을까 생각하여 풀이했다.

예제는 아래와 같다.
1. 55-50+40-20+30+30
2. 55-(50+40)-(20+30+30)
3. 55-90-80 = -115

1. split을 통해 더하기 수식들만 분리
2. '-' 기호 기준으로 분리된 배열을 반복분을 통해 0번째 인덱스를 제외하고 나머지는 빼기 연산을 진행
3. 반복문 중 빼기 연산 전 splitSum() 함수를 통해 분리된 더하기 수식을 형변환을 통해 실제로 더하여 리턴

LostParenthesis.java

package com.example.Baekjoon;

/**
 * 잃어버린 괄호
 * 그리디 알고리즘으로 풀이
 * String formula -> 수식 문자열
 */
public class LostParenthesis {
    public int getMinByFormula(String formula) {

        int answer = 0;
        // 1. 제일 큰 값을 빼줄 수 있도록 - 기준으로 split
        String[] splitedFormulas = formula.split("-");

        for (int i = 0; i < splitedFormulas.length; i++) {
            int intFormula = splitSum(splitedFormulas[i]);

            // 처음 값이면 더하기(0번째 인덱스 값은 앞에 기호가 없는 값이므로)
            if (i == 0) {
                answer += intFormula;
            } else {
                answer -= intFormula;
            }
        }
        return answer;
    }

    private int splitSum(String formula) {
        // 2. + 수식으로 묶여있는 문자열을 형변환 후 더하기
        int sum = 0;
        String[] splitedFormulas = formula.split("\\+");

        for (String strFormula : splitedFormulas) {
            sum += Integer.parseInt(strFormula);
        }

        return sum;
    }
}

LostParenthesisTest.java

package com.example.Baekjoon;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class LostParenthesisTest {
    @Test
    public void testLostParenthesis() {

        LostParenthesis lp = new LostParenthesis();

        String formula1 = "55-50+40";
        String formula2 = "10+20+30+40";
        String formula3 = "00009-00009";

        int result1 = lp.getMinByFormula(formula1);
        int result2 = lp.getMinByFormula(formula2);
        int result3 = lp.getMinByFormula(formula3);

        assertEquals(-35, result1);
        assertEquals(100, result2);
        assertEquals(0, result3);
    }
}