[백준(baekjoon) 1541] 잃어버린 괄호

문제

백준 1541

‘+’,’-‘, 양수로 이루어진 식(최대 길이 50)이 입력 되었을 때,
괄호를 적절히 식의 최종 값을 최소로 만든 후 그 값을 출력 하시오.

해결

두가지 방식으로 풀었는데 둘다 원리는 동일하다.
단지 for문을 한번만 쓰고 싶어서 좀 더 줄여 보았다.

1) 방식은 Stack을 이용한 중위 표기법 계산 방식 사용, 2중 for문을 사용하였다.
2) 방식은 for문을 한번만 사용하고, Stack을 따로 쓰지 않았다.

원리는 이러하다.

1. 입력 값을 숫자, 연산자로 구분한다.
   
   • 입력 값이 30+40-29형식으로 붙어서 한줄로 들어오기 때문에, char로 한 문자씩 딴다.
   • 연산자를 기준으로 숫자를 구분, 저장한다.
   • 1) 방식의 경우 첫번 째 for문 에서는 그냥 숫자, 연산자를 Stack에 저장해두는 과정만 처리하였다.
   • 2) 방식의 경우 연산자일 때 이전의 숫자에 대한 연산 처리를 하였다.
2. 값을 최소로 만들기 위해 - 연산자를 활용한다.
   
   • 간단히, 큰 음수 값을 만든다고 생각하면 된다. 그러기 위해선 - 를 기준으로 괄호를 쳐주면 된다.
   • 예를들어, 100-20+40+50-55+20은 (100)-(20+40+50)-(55+20)
   • 1) 은 Stack을 활용한 중위 표기법 계산 방식으로 뒤에서 부터 처리하여 묶어 주었다.
   • 2) 는 앞에서 부터 처리하여, -를 기준으로 모든 값들을 괄호로 묶어서 sum변수에 저장해주며 처리하였다.
   • 1) , 2) 방식에 대한 추가 설명은 코드의 주석으로 설명해두겠다.

알고리즘

그리디 알고리즘을 사용해 해결하였다.

그리디 알고리즘에 대해 잘 모르신다면 이 글을 참고하세요!

구현 java

1) 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        String input = sc.nextLine();
7.
8.        Stack<Integer> nums = new Stack<>(); // 숫자를 넣어둘 스택
9.        Stack<Character> operators = new Stack<>(); // 연산자 넣어둘 스택
10.        int num = 0;
11.        for (char c : input.toCharArray()) {
12.            if (c == '-' || c == '+') {
13.                operators.push(c);
14.                nums.push(num);
15.                num = 0; // 새로운 숫자를 받기 위해서
16.            } else num = num * 10 + (c - '0');
17.        }
18.        nums.push(num);
19.
20.        int answer = 0;
21.            /*
22.            입력 값 기준으로 뒤에서 부터 차례대로 처리하게 된다.
23.            + 는 일단 더해서 넣고 - 는 뒤에서 부터 다 더해진 값을 그냥 꺼내 최종 값에 빼준다.
24.             */
25.        while (!operators.isEmpty()) { // 연산자 기준으로 처리
26.            char oper = operators.pop();
27.            int su = nums.pop(); // 우선 숫자 하나는 무조건 활용하니 꺼내 놓는다.
28.            if (oper == '-') answer -= su;
29.            else nums.push(su + nums.pop());
30.        }
31.        System.out.println(answer + nums.pop()); // 숫자가 하나 더 많고 해당 값은 항상 양수이므로 더해준다.
32.    }
33.}

2) 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        String input = sc.nextLine();
7.
8.        int num = 0; // 입력 숫자 구분용
9.        int sum = 0; // +연산을 위한 변수(괄호 안 숫자 합산용)
10.        int answer = 0; // 최종 정답
11.            /*
12.             해당 flag는 - 부호가 나와서 앞서 계산된 값을 저장할 때,
13.             해당 값의 부호를 나타내는 기호이다.
14.             첫번째 값은 무조건 양수이므로 +인 true이고,
15.             이후 한번이라도 -가 나온 경우 false를 유지한다.
16.             중간에 나오는 +연산은 -를 위해 더 해주기만 할 뿐이므로 true로 바꾸지 않는다.
17.              */
18.        boolean flag = true; // +일 경우 true, -일 경우 false
19.        for (char c : input.toCharArray()) {
20.            int su = c - '0';
21.            if (su < 0) {
22.                sum += num; // 부호가 나오면 일단 sum에 더해준다. (-는 앞의 값에 영향을 주지 않음)
23.                num = 0; // 부호가 나왔으므로 새로운 숫자를 위해 초기화
24.                if (c == '-') {
25.                    // -가 나오면 flag에 따라 최종 값에 더해준다.
26.                    if (flag) answer += sum; // 음수
27.                    else answer -= sum; // 양수
28.                    sum = 0; // 괄호가 시작되었으므로 초기화 한다.
29.                    flag = false;
30.                }
31.            } else num = num * 10 + (c - '0');
32.        }
33.        sum += num; // 마지막 숫자 괄호 안 합산
34.        System.out.println(answer + (flag ? sum : -1 * sum)); // 부호에 따라 마지막 값 처리
35.    }
36.}

결과

1. 2) 방식 : for문을 한번만 사용하고, Stack을 따로 쓰지 않음.
2. 1) 방식 : Stack 사용, 2중 for문을 사용

하지만 입력 값이 50길이를 넘지 않아 큰 차이가 없다…