[BOJ] 1541번 잃어버린 괄호

개요

최적의 괄호 씌우는 방법을 찾아내 풀이하는 그리디 알고리즘 문제

문제링크

코드

import java.io.*;

public class Baekjoon1541 {
    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 read = br.readLine();
        StringBuilder sb = new StringBuilder();
        boolean prevMinus = false;
        boolean prevDigit = true;
        int temp,result = 0;
        for (int i = 0; i < read.length(); i++) {
            char c = read.charAt(i);
            if(Character.isDigit(c)) {
                sb.append(c);
            }
            else {  //연산자
                if(prevDigit) { //이전값이 숫자이면
                    temp = Integer.parseInt(sb.toString());
                    result += temp;
                    sb = new StringBuilder();
                }
                if(c == '+') {
                    if(prevMinus)
                        sb.append('-');
                }
                else {  // '-'
                    prevMinus = true;
                    sb.append('-');
                }
            }
        }
        temp = Integer.parseInt(sb.toString());
        result += temp;
        bw.write(result+"\n");
        bw.flush();
    }
}

해결 과정

+와 -만 존재하는 식에서 어디에 괄호를 붙여서 식의 값을 최소한으로 만드는지에 대한 문제이다.

값을 최소로 만들려면 빼주는 숫자를 최대한으로 만들어주면 되는데, 식을 앞에서부터 하나씩 보다가 마이너스를 만나면 다음에 플러스를 만나기 전까지의 숫자들을 모두 괄호로 묶어주면 된다.

최적의 해를 찾는 방법만 알아내면 구현은 쉬운 문제였다.

결과