[백준] boj 1541 java "잃어버린 괄호" - 그리디 알고리즘

잃어버린 괄호 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

42234

20808

16706

49.102%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

55-50+40

예제 출력 1 복사

-35

예제 입력 2 복사

10+20+30+40

예제 출력 2 복사

100

예제 입력 3 복사

00009-00009

예제 출력 3 복사

0

---

 

문제 접근 방식

이문제는 + 와 - 밖에 없는 최솟값을 구하는 문제이다,

처음에는 브루트포스인줄 알고 괄호의 모든 경우를 구해줄려했지만 굳이 그럴 필여없다.

-가 나오면 -그룹을 괄호 쳐주고, 아니면 더해주면 된다.

 

[1번 코드]

요래 풀었는데, 풀고 찾아보니 더 나이스한 방법이 있었다, 아래로

package solved.Class;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String operator = "+-";

        String temp[] = br.readLine().split("");

        int result = 0;
        int minus_group=0;

        String now_operator="+";
        String number="";

        for(String now : temp){
            //연산자
            if(operator.contains(now)) {
                if(now_operator.equals("+")) {
                    result += Integer.parseInt(number);
                    if(now.equals("-"))
                        now_operator="-";
                }
                else{
                    minus_group+=Integer.parseInt(number);
                    if(now.equals("-")){
                        result-=minus_group;
                        minus_group=0;
                    }
                }
                number="";
            }
            //숫자
            else
                number+=now;
        }
        if(now_operator.equals("+"))
            result+=Integer.parseInt(number);
        else{
            minus_group+=Integer.parseInt(number);
            result-=minus_group;
        }
        System.out.println(result);
    }
}

 

[2번 코드]

-단위로 끝으면 알아서, 괄호가 완성된다.

-별로 더하고, 나눠진 값들을 더해주면 끝,,, 이 사람은 천재야

package solved.Class;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String temp[] = br.readLine().split("-");

        int result= add(temp[0]);

        for(String a: temp)
            System.out.println(a);

        for(int i=1;i<temp.length;i++)
            result-=add(temp[i]);
        System.out.println(result);

    }

    public static int add(String str){
        // \\-> 특수문자
        String tempp[] = str.split("\\+");
        int result = 0;

        for(String s : tempp)
            result+=Integer.parseInt(s);

        return result;
    }
}