백준 1541 잃어버린 괄호 Java

그리디 알고리즘 문제인 잃어버린 괄호 문제이다.

 

입력으로 어떠한 식이 한 줄 주어졌을 때 괄호를 적절히 쳐서 값을 최소로 만들면 되는 문제이다.

 

예제만 보고도 알 수 있듯이 값을 최소로 만들기 위해서는 괄호를 마이너스 뒤에 치면 된다.

 

String으로 식을 입력 받고

-,+를 저장하는 배열을 따로, 수를 저장하는 배열을 따로 만든다.

어떠한 수가 한 자리이든 두 자리이든 수의 다음엔 무조건 +또는- 가 오므로

+와-를 만날 때 까지 숫자를 String으로 계속 합치고

+와-를 만나면 숫자를 저장하는 배열에 넣어준다.

마찬가지로 +나- 또한 같이 다른 배열에 넣어준다.

 

그리고 연산자배열과 수를 저장한 배열을 동시에 하나 씩 꺼내서 확인한다.

이 때 처음으로 - 연산자를 만나면 그때부터는 수를 전부 빼주면 된다.

왜냐하면 괄호가 쳐져 있게 때문에 결국엔 괄호 안에 있는 값들을 합한 값을 빼주는 결과이기 때문이다.

 

주의 할점은 연산자 배열과 수를 저장한 배열에서 하나씩 빼서 확인하기 때문에

두 배열의 크기는 같아야 한다.

55-50+40

연산자는 2개 이므로 처음에 55앞에 +가 있다고 가정하고 +를 넣어주고

연산자를 만날 때마다 만들어둔 수를 저장하므로

반복문이 끝나면 수를 저장한 배열에 마지막으로 만들어둔 수를 저장한다.

 

+와 -만 구별하면 되므로 연산자배열에는 +를1로 -를-1로 저장한다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        List<Integer> sign = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
 
        String k = "";
        sign.add(1); //처음엔 플러스를 넣어준다.
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i)=='+'||s.charAt(i)=='-') {
                if(s.charAt(i)=='+')
                    sign.add(1);
                else if(s.charAt(i)=='-')
                    sign.add(-1);
                list.add(Integer.parseInt(k));
                k = "";
            } else {
                k += s.substring(i,i+1);
            }
        }
        
        list.add(Integer.parseInt(k)); //마지막 수를 저장
        int ans = 0;
        boolean minus = false;
        for(int i=0; i<list.size(); i++) {
            if(sign.get(i) == -1)
                minus = true;
            
            if(minus)
                ans -= list.get(i);
            else
                ans += list.get(i);
        }
        System.out.println(ans);
    }