[S2] 잃어버린 괄호 : 1541 - 그리디

문제

1541번: 잃어버린 괄호

 

 

생각 흐름

우선 최소가 되는 상황을 생각했다. 최소가 되는 상황은 -기호가 나오고 + 기호가 나오면 빼줄 때 최소 값이 된다. -기호가 나오고 -기호가 나오면 마찬가지로 빼준다. 우선 로직은 이 정도로 생각했다.

 

 

구체적인 해결 로직

입력 데이터 처리 

입력은 한줄로 +, - 기호와 숫자가 섞여 주어진다. 이 데이터를 어떻게 처리할 지 고민하다 char[] 을 이용하여 구별 한 후,

숫자와 기호 리스트를 생성하여 데이터를 추가했다. 

	br = new BufferedReader(new InputStreamReader(System.in));
        String mathMatic = br.readLine();

        ArrayList<Character> operator = new ArrayList<Character>();
        ArrayList<Integer> nums = new ArrayList<Integer>();

        char [] charN = new char[6];
        int numSize = 0;

        // 입력 데이터 생성
        for(int i=0; i< mathMatic.length(); i++) {
            char currentChar = mathMatic.charAt(i);
            if(currentChar == '+' || currentChar == '-'){
                if(numSize != 0){
                    nums.add(charArrToInteger(charN));
                    charN = new char[6];
                    numSize = 0;
                }
                operator.add(currentChar);
            }
            else{
                charN[numSize++] = currentChar;
            }
        }
        nums.add(charArrToInteger(charN));


 public static int charArrToInteger(char[] chars){
        String strN = "";
        int i = 0;
        while(chars[i] != 0 && i < chars.length){
            strN += Character.toString(chars[i]) ;
            i++;
        }
        return  Integer.parseInt(strN);
    }

 

 

핵심 로직

+ 기호가 나오면 - 기호가 나올 때까지 더해주고, -기호가 나오면 -기호가 나올 때까지 빼준다. 생각을 해보니 - 기호 다음에 -기호가 나오면 똑같이 빼주면 된다. 그러므로 이 문제는 - 기호가 나오면 그 이후부터 나온 모든 수를 빼주면 된다.

	char preOper = 0;
        result += nums.get(0);
        if(operator.size() > 0 )
            preOper = operator.get(0);

        int i =1;
        while(i < nums.size()){
            if(i-1 >= operator.size())
                break;

            if(preOper == '+'){
                if(operator.get(i-1) == '-'){
                    preOper = '-';
                    result -= nums.get(i);
                }else{
                    result += nums.get(i);
                }

            }
            else{
                result -= nums.get(i);
            }
            i++;
        }

 

 

 

전체 코드

package Success;

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

public class BOJ_1541 {

    public static BufferedReader br;
    public static int result = 0;
    public static void main(String [] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        String mathMatic = br.readLine();

        ArrayList<Character> operator = new ArrayList<Character>();
        ArrayList<Integer> nums = new ArrayList<Integer>();

        char [] charN = new char[6];
        int numSize = 0;

        // 입력 데이터 생성
        for(int i=0; i< mathMatic.length(); i++) {
            char currentChar = mathMatic.charAt(i);
            if(currentChar == '+' || currentChar == '-'){
                if(numSize != 0){
                    nums.add(charArrToInteger(charN));
                    charN = new char[6];
                    numSize = 0;
                }
                operator.add(currentChar);
            }
            else{
                charN[numSize++] = currentChar;
            }
        }
        nums.add(charArrToInteger(charN));


        char preOper = 0;
        result += nums.get(0);
        if(operator.size() > 0 )
            preOper = operator.get(0);

        int i =1;
        while(i < nums.size()){
            if(i-1 >= operator.size())
                break;

            if(preOper == '+'){
                if(operator.get(i-1) == '-'){
                    preOper = '-';
                    result -= nums.get(i);
                }else{
                    result += nums.get(i);
                }

            }
            else{
                result -= nums.get(i);
            }
            i++;
        }

        System.out.println(result);
    }

    public static int charArrToInteger(char[] chars){
        String strN = "";
        int i = 0;
        while(chars[i] != 0 && i < chars.length){
            strN += Character.toString(chars[i]) ;
            i++;
        }
        return  Integer.parseInt(strN);
    }

}