백준 1541번 문제

풀이

• 연산자 +, - 만 가지고 기준을 잡아 최솟값을 만드는 문제
• 문자열을 사용한 Greedy Algorithm을 유도하는 문제
• 정답을 최솟값을 만들어야 하기 때문에 Greedy Algorithm을 사용

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 예제 문자열
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String calc = String.valueOf(bf.readLine());
        //55-50+30+40-
        String[] substractPart =  calc.split("-");
        int sum = 0; int result = 0;
        int n = 0;

        for (String part: substractPart) { //  50 -> 40 20 -> 30 40 20 -> 30
            if(part.contains("+")) {
                String[] plusPart = part.split("\\+");
                for (int i = 0; i < plusPart.length; i++) {
                    sum += Integer.parseInt(plusPart[i]);
                }
                if(n < 1) {
                    result = sum;
                    sum=0;
                }
            }
            else {
                if (n < 1) {
                    result = Integer.parseInt(part);
                }
                else {
                    sum += Integer.parseInt(part);
                }
            }
            n++;
        }
        if (n > 1) result -= sum;
        bw.write(result+"");
        bw.flush(); bw.close(); bf.close();
    }
}

1. 계산식 설정

String calc = String.valueOf(bf.readLine());
        //55-50+30+40-
String[] substractPart =  calc.split("-");
int sum = 0; int result = 0;
int n = 0;

• +, - 도 입력을 받기 때문에 String 형으로 입력 받음
• 최솟값을 만들기 위해선 - 기준으로 묶어야 최솟값이 만들어 질 수 있음, 여기서 Greedy Algorithm 사용 (ex) 10 - (5 + 3 + 6) == -4 && 10 - 5 + (3 + 6) == 14)
• sum 은 괄호 안의 계산식의 합의 변수, result 는 최종 결과의 변수, n은 초기 값 설정 및 계산 설정을 위한 변수

2. - 기준으로 나눈 괄호 계산

for (String part: substractPart) { //  50 -> 40 20 -> 30 40 20 -> 30
    if(part.contains("+")) {
        String[] plusPart = part.split("\\+");
        for (int i = 0; i < plusPart.length; i++) {
            sum += Integer.parseInt(plusPart[i]);
        }
        if(n < 1) {
            result = sum;
            sum=0;
        }
    }
    else {
        if (n < 1) {
            result = Integer.parseInt(part);
        }
        else {
            sum += Integer.parseInt(part);
        }
    }
    n++;
}

• '-' 기준으로 split을 나눈 '+'가 포함된 String 형을 계산하기 위해 +로 다시 split
• '+' 가 포함 안될 시 else문으로 처리
• '+' 로 split 된 숫자들을 sum 변수에 대입 연산
• 만일 계산식이 처음이라면 n 변수를 이용해 초반 값 설정 (예를 들어 1+2+3+4 - (1 + 3 + 5) 라면 1, 2, 3, 4가 시작 값이 되어야 함)
• 만일 '-' 기준으로 나눈 값이 '+' 연산자가 없고 계산식이 처음이라면 for each문으로 나눠진 part가 그대로 result에 삽입
• 처음이 아니라면 sum에 대입 연산을 수행

3. 결과 값 도출

if (n > 1) result -= sum;
bw.write(result+"");

• 괄호 안의 '+' 연산을 끝내고 나왔다면 최종적으로 '-' 연산 수행
• 입력 값을 숫자 하나만 받았다면 n은 최종적으로 1이 되므로 연산을 수행하지 않고 그대로 결과 값 도출