[JAVA] 백준 1541 그리디

 

 

 

1541번: 잃어버린 괄호

문제

수식이 주어졌을 때 괄호를 삽입해 식의 최솟값을 구하여라.

풀이

“-”를 기준으로 자르고 합을 모두 계산한 다음 뺄셈연산을 진행해주는 것이 가장 작은 값이라고 생각했다.

1. “-”를 기준으로 문자열을 자른다.
2. “+”를 기준으로 문자열을 잘라 모든 값을 더해준다.
3. 더한값들을 모두 빼준다.

값 입력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "-");

        String[] A = new String[st.countTokens()];

        for(int i=0; i<A.length; i++){
            A[i] = st.nextToken();
        }

“-” 기준으로 문자열을 잘라서 담는다.

• “-”기준으로 괄호를 친다.
• (ex: 입력으로 “55-50+40”이 들어오면 “55-(50+40)”이 된다고 생각하면 된다.)

덧셈 연산

        for(int i=0; i<A.length; i++){
            st = new StringTokenizer(A[i], "+");
            int sum = 0;
            while (st.hasMoreTokens()){
                sum += Integer.parseInt(st.nextToken());
            }
            A[i] = sum+"";
        }

문자열을 “+”기준으로 잘라서 값을 더한 후 배열에 다시 넣어준다.

뺄셈 연산

        int answer = Integer.parseInt(A[0]);
        for(int i=1; i<A.length; i++){
            answer -= Integer.parseInt(A[i]);
        }

첫 번째 값은 “-”가 나올 수 없기 때문에 첫 번째 배열에 모든 배열의 값을 빼준다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "-");

        String[] A = new String[st.countTokens()];

        for(int i=0; i<A.length; i++){
            A[i] = st.nextToken();
        }

        for(int i=0; i<A.length; i++){
            st = new StringTokenizer(A[i], "+");
            int sum = 0;
            while (st.hasMoreTokens()){
                sum += Integer.parseInt(st.nextToken());
            }
            A[i] = sum+"";
        }

        int answer = Integer.parseInt(A[0]);
        for(int i=1; i<A.length; i++){
            answer -= Integer.parseInt(A[i]);
        }

        System.out.println(answer);

    }
}

결과