[백준] 잃어버린 괄호 JAVA

반응형

728x90

[백준] 잃어버린 괄호

---

접근

• dfs
• 그리디

---

풀이

수식을 입력받아 괄호를 적절히 추가해 최솟값을 만드는 문제이다. 처음에 문제를 읽고 접근을 잘못된 방향으로 해버려 통째로 갈아엎고 다시 풀었던 문제이다. 이전에 dfs와 bfs문제를 풀며 남은 코드를 활용하고자 모든 경우의 수 중 최솟값을 구하는 방식으로 진행했다.

 

우선 잘못 풀었던 방법은 일단 수식을 +와 -, 연산자가 나올 때 마다 문자열을 잘라주었다. 그리고 만들어진 문자열을 가지고 정수로 변환하는데 숫자 앞에 나온 연산자가 +라면 양수로 -라면 음수로 만들어 버렸다. 즉 55-50+40이라는 수식이 있을 경우 {"55", "-", "50", "+", "40"}으로 잘라준 뒤 {55, -50, 40}이라는 배열로 만들었다. 이 배열을 가지고 인덱스가 2이상 차이 나는 경우 괄호로 묶을 수 없기 때문에 1이하로 차이가 나는 경우만 추가해가며 탐색을 돌렸는데 당연히 틀리고 말았다.부호를 붙인 정수를 만든것 부터 잘못되었던 것이다. 부호를 붙여 버린다면 괄호가 의미가 없다는 것을 테스트를 돌려본 후에 깨달았다. 부호가 있다면 순서를 아무리 바꿔봤자 결론적으로 다 더하기 연산이 되어버리는 것이었다. a + b + c의 값이나 b + a + c의 값이 똑같은 것처럼 부호를 빼버리며 모두 + 연산이 되어버려 무의미한 탐색이 된 것이다.

 

코드를 통째로 갈아엎고 새로운 접근 방식을 생각했다. 물론 dfs로 부호를 빼지 않고 풀이가 가능하겠지만 수정보다 새로 짜는것이 맘 편하기도 하고 오류도 적다. 연산 결과가 최솟값이 될려면 빼는 수가 빼는 대상이 되는 수보다 커야한다. 감수가 피감수보다 커야 작은 값이 나온다는 말인데 그렇게 되기 위해서는 - 연산자가 나오는 부분을 기준으로 잘라서 뒷 부분을 모조리 더해 감수를 최대한 크게 만들어 주는 것이 포인트라고 볼 수 있다. 현재 방식에 최선의 선택을 하는 그리디 접근 방식이라고 할 수 있다.

String[] minusParts = expression.split("-");

입력받는 연산식은 - 연산자를 기준으로 잘리게 된다. 55-50+40이라면 {55, 50+40}의 형태로 저장된다.

private static int evaluate(String expression) {
        String[] plusParts = expression.split("\\+");
        int sum = 0;
        for (String part : plusParts) {
            sum += Integer.parseInt(part);
        }
        return sum;
    }

- 연산자의 뒷 부분들을 계산해 줄 함수를 따로 뽑았다. - 연산자의 뒷 부분들은 +연산자만 있는 작은 수식이라고 볼 수 있어 그 부분을 더해 1개의 감수로 만들어주는 과정이다. + 연산자를 기준으로 잘라 숫자를 분리해주고 다 더해준 뒤 반환한다.

int result = evaluate(minusParts[0]);

for (int i = 1; i < minusParts.length; i++) {
	result -= evaluate(minusParts[i]);
}

- 연산자가 나오기전 앞의 식들을 계산하여 담아준다. - 연산자가 나오기 전에 잘려진 부분은 다 +로만 이루어져있기 때문에 더해 피감수로 만들어 준다. 그리고 남은 뒷 부분들을 똑같이 더해준 뒤 피감수에서 빼주는데 배열에 들어있는 식들이 - 연산자를 만나서 잘린 부분들이기 때문에 하나의 숫자로 합쳐 빼주는 것이다. 10+20+30-10+60+12-15-25+20이라는 수식이 있다면 (10+20+30)-(10+60+12)-(15)-(25+20)의 덩어리로 계산되어, 결국 60-82-15-45 = -82 라는 결과를 얻게 되는 것이다.

---

전체 코드

import java.util.Scanner;

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

        String[] minusParts = expression.split("-");

        int result = evaluate(minusParts[0]);

        for (int i = 1; i < minusParts.length; i++) {
            result -= evaluate(minusParts[i]);
        }

        System.out.println(result);
    }

    private static int evaluate(String expression) {
        String[] plusParts = expression.split("\\+");
        int sum = 0;
        for (String part : plusParts) {
            sum += Integer.parseInt(part);
        }
        return sum;
    }
}