[백준_1541] 잃어버린 괄호 ( Greedy )

[1]  문제

[2] 접근법

[1] 최소 값에 접근하는 방식

 

우리가 생각 해야하는 가장 첫 번째 문제는 "어떻게 최소 값을 만들 수 있을까?" 에 대한 의문을 해결 해야 할 것이다.
예시로 주어진 내용을 보면 55 - 50 + 40 이고, 괄호를 묶는 방식에 따라 (55-50)+40 = 45 // 55-(50+40) = -35 라는 다른 결과 값을 얻을 수 있다. 이 때, 괄호를 각각 묶으면서 배울 수 있었던 점은 '-'를 기반으로 나누고 +로 되있는 친구들끼리 미리 더한 후에 빼면 최소 값을 얻을 수 있다는 생각을 가질 수 있게 되었다. 

 

• 예시 문제 : 30-50-20+40+20-90+100+10+20-200 
• 이 때 최소 값을 구하기 위해서는 '-'를 기준으로 분리하고, +인 친구들은 먼저 더 해주면 된다.
• 괄호로 표시를 하면 30 - 50 -(20+40+20) - (90+100+10+20) - 200 다음과 같다

[2] 구현

 

그렇다면 우리는 이 것을 어떻게 구현 할 수 있을까? 내가 찾아낸 방법은 크게 1) Split 2) StringTokenizer 을 쓰는 방법을 나뉘었다. 하단의 코드를 통해 두 가지의 사례에 대해 모두 다뤄보고자 한다.

 

[3] 코드

[1] Split

import java.io.InputStreamReader;
import java.io.IOException;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sum = Integer.MAX_VALUE;
        String[] substraction = br.readLine().split("-"); // -를 기준으로 나눔

        for ( int i =0; i < substraction.length; i++) {
            int temp = 0;
            String []add = substraction[i].split("\\+"); // + 를 기준으로 나누고

            for ( int j = 0; j < add.length; j++) {
                temp += Integer.parseInt(add[j]); // 그 값들을 모두 temp에 더한다.
            }
            
            if ( sum == Integer.MAX_VALUE)
                sum = temp;
            else
                sum -= temp;

        }
        System.out.println(sum);
    }
}

 

 

 

[2] StringTokenizer

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sum = Integer.MAX_VALUE;
        StringTokenizer substarction = new StringTokenizer(br.readLine(), "-");

        while(substarction.hasMoreTokens()) {
            int temp = 0;
            StringTokenizer addition = new StringTokenizer(substarction.nextToken(), "+");
            while (addition.hasMoreTokens()) {
                temp += Integer.parseInt(addition.nextToken());
            }
            if ( sum == Integer.MAX_VALUE)
                sum = temp;
            else
                sum -= temp;
        }
        System.out.println(sum);
     }
}