[백준] 1541번 : 잃어버린 괄호 - 자바(Java)

Problem 🔒

문제

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

 

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1

55-50+40

예제 출력 1

-35

예제 입력 2

10+20+30+40

예제 출력 2

100

예제 입력 3

00009-00009

예제 출력 3

0

---

Approach 1 ⭕ - Math.pow() 활용

처음 문제를 읽고, 예제를 봤을 때 왜 답이 -35가 나오는지 이해할 수 없었다.

55-5(0+40) = 55-5+40 이런식으로는 변경할 수 없으며, 연속되는 숫자는 통째로 하나의 숫자로 처리해야한다. 그렇기에 55-(50+40)으로 답이 -35가 나오게 된다.

따라서 이 식의 값이 최소가 되기 위해서는 -뒤에 나오는 숫자가 커지게 만들어야 한다.

1. 문자열을 ‘-’를 기준으로 분리한다.
   • 55-50+40의 예제가 있다고 하면
   • [”55” , “50+40”] 이렇게 분리하여 배열에 저장한다.
2. 분리한 각 배열마다 다시 ‘+’를 기준으로 분리하여 덧셈 연산을 처리한다.
   • 이때 ‘+’는 특수문자여서 이스케이프(\\)처리를 해줘야한다.
   • 예제의 경우 [”55”], [”50”, “40”]으로 분리된다.
3. 배열을 순회하며 int형으로 바꿔 누적 합을 구해, ans에서 빼준다.
   • 첫 번째 그룹은 결과 ans에 더하고, 이후 그룹은 빼기 연산을 수행한다.
   • 배열의 각 문자열 요소(55)를 하나씩 가져와서, 자릿수를 고려하여 숫자를 변환한다.
   • 문자를 숫자로 변환 : 십의자리 char 5를 -’0’으로 숫자로 변환한다.
   • 자릿수 계산 : 10의 (문자열 길이-(인덱스+1)) 거듭제곱을 곱해 계산한다.

---

Approach 2 ⭕ - Integer.parseInt() 활용

1. 숫자 합산 방식 효율적으로 수정
   • 위의 로직은 숫자 변환을 수동으로 처리했지만, Integer.parseInt()를 사용하여 숫자변환을 효율적으로 합산할 수 있다.

Integer.parseInt() 사용으로 코드 길이가 많이 줄어듦을 알 수 있었다.

그리고 split할 때, 구분자가 문자열에 없어도 오류 나지 않음을 알 수 있었다.

---

Solution 💡

public class 그리디 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        // 1. "-"로 문자열을 분리하여 배열에 저장한다
        String[] nums = str.split("-");
        int ans = 0;
        // 2. 배열마다 식을 계산하여 ans에서 빼준다.(첫 번째 값은 더함)
        for(int i=0; i<nums.length; i++){
            // 3. 각 배열마다 "+"로 문자열을 분리하여 계산한다.
            // "+"는 정규식에 사용되는 특수문자여서 이스케이프(\\\\)처리가 필요하다.
            String[] splitP = nums[i].split("\\\\+");
            int tmp = 0;
            // 4. "+"로 분리된 문자열의 수를 구하여 tmp에 더해준다.
            for(int j=0; j<splitP.length; j++){
                String num = splitP[j];
                for(int k=0; k< num.length(); k++){
                    tmp += (num.charAt(k)-'0')*Math.pow(10,splitP[j].length()-(k+1));
                }
            }
            if(i==0) ans += tmp;
            else ans -= tmp;
        }
        System.out.println(ans);
    }
}

Integer.parseInt

public class 그리디 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        String[] nums = str.split("-");
        int ans = 0;
        for(int i=0; i<nums.length; i++){
            String[] splitP = nums[i].split("\\\\+");
            int tmp = 0;
            for(int j=0; j<splitP.length; j++){
                tmp += Integer.parseInt(splitP[j]);
            }
            if(i==0) ans += tmp;
            else ans -= tmp;
        }
        System.out.println(ans);
    }
}