알고리즘 풀이 - 백준 1541(잃어버린 괄호, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

+, - 또는 0~9까지의 최대 5번 이어진 숫자로만 이어진 방정식이 있을 때, 괄호를 적절히 넣어 최소값이 되는 경우의 결과를 구하는 문제

 

 

2. 풀이

 

아래의 예시를 보자.

1 + 2 - 3 + 4 - 5 + 6 + 7 + 8 - 9 + 10

 

위의 식에서 최소값이 되게 하는 경우는 다음과 같이 괄호를 지정했을 때이다.

1 + 2 - (3 + 4) - (5 + 6 + 7+ 8) - (9 + 10)

 

즉, 최소값이 되기 위해서는 -기호 이후에 차감을 하는 숫자가 최대한 커지도록 해야 한다. 따라서 - 이후에는 +로 연산되는 모든 숫자를 더하고 그 뒤에 빼주는 방식으로 저장하여 문제를 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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));
        String equation = br.readLine();
        Deque<Integer> num = new ArrayDeque<>();
        Deque<Character> sign = new ArrayDeque<>();
        
        int current = 0;
        char lastSign = ' ';
        for(int i=0; i < equation.length(); i++){
            char c = equation.charAt(i);
            
            // 부호가 나온 경우
            if(c == '+' || c == '-'){
                // 이전의 마지막 부호가 +였다면
                if(lastSign == '+'){
                
                    // 이전 숫자에 현재 값을 더하여 Deque에 넣어준다.
                    num.offerLast(num.pollLast() + current);
                    
                // 이전의 마지막 부호가 -였다면
                } else {
                    
                    // 현재 값을 바로 Deque에 넣는다.
                    num.offerLast(current);
                }
                
                // 마지막 나타난 부호를 업데이트 한다.
                lastSign = c;
                current = 0; // 현재 숫자는 0으로 다시 변환
                
            // 숫자가 나왔다면 부호가 나올 때까지 10을 곱하고 현재 숫자를 더한다.
            } else {
                current = current * 10 + (c - '0');
            }
        }
        
        // 마지막에 나오는 숫자는 외부에서 동일하게 처리
        if(lastSign == '+'){
            num.offerLast(num.pollLast() + current);
        } else {
            num.offerLast(current);
        }
        
        // 기존 값이 최대값이면 첫 수로 지정하고 이후의 값은 모두 뺀다.
        int ans = Integer.MAX_VALUE;
        while(!num.isEmpty()){
            int n = num.pollFirst();
            if(ans == Integer.MAX_VALUE){
                ans = n;
            } else {
                ans -= n;
            }
        }
        System.out.println(ans);
        br.close();
    }
}

 

위의 코드는 제가 문제를 풀기 위해 사용한 코드이며, 다른 분의 코드 중 아주 아름답게 짧게 푼 코드가 있어 참조 차 기록하기 위해 아래에 가져왔습니다.

아래와 같은 방식으로 좀 더 사고하고 쉽게 풀 수 있는 능력을 기를 수 있으면 좋을 것 같습니다. ㅎㅎ

제가 주석을 추가하였기에 약간 길어졌는데 아래의 코드를 참고 부탁 드립니다.

 

백준 ID scala0114 님의 공개된 코드를 가져왔습니다.

import java.io.BufferedReader;
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));
        
        // 우선 "-" 기호를 기준으로 나눕니다.
        String[] inputs = br.readLine().split("-");
        
        String[] oprdList;
        int answer = Integer.MIN_VALUE, tmp = 0;
        
        // - 기호로 나누어진 부분 방정식을 계산하여 서로 빼주는 작업을 해주는 부분
        for(String expr:inputs) {
        
            // + 기호를 기준으로 값을 나눈다. (숫자만 남게 된다.)
            oprdList = expr.split("\\+");
            
            // 숫자들을 다 더한다.
            for(String oprd:oprdList)
                tmp += Integer.parseInt(oprd);
                
            // 최초 값이면 그대로 넣고 아니면 계속 뺄셈 수행
            if(answer == Integer.MIN_VALUE)
                answer = tmp;
            else
                answer -= tmp;
            tmp = 0;
        }
        
        
        System.out.print(answer);
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.