[백준] 16639번: 괄호 추가하기 3

문제 (Gold 1)

 

https://www.acmicpc.net/problem/16639

16639번: 괄호 추가하기 3

---

풀이

• 숫자와 연산자를 한번에 저장할 수 있는 Expression 클래스 생성
  -> 숫자를 char로 한번에 저장했더니, 9 이상의 숫자는 제대로 작동하지 않음 ㅠㅠ
• 연산 리스트에서 숫자가 나오는 짝수 인덱스를 돌며 연산 수행 후, 남은 연산 리스트를 재귀 돌림
  1. 기저조건: 리스트에 원소 하나만 남아있을 때 ( == 숫자 하나가 남아있을 때 )
  2. 짝수 idx( 숫자가 있는 idx )를 돌면서 반복문 실행 
  3. 해당 인덱스부터 숫자(i), 연산자(i+1), 숫자(i+2)를 차례로 추출 
  4. 추출 후, 리스트에서 삭제
     -> 기존 리스트에서 삭제 시, 다음 연산에 영향을 줌으로 복사한 리스트에서 로직 수행
  5. 연산자에 따라 연산 수행ㅁ
  6. 연산 수행 결과를 i번째 인덱스에 저장
  7. 연산자 리스트를 재귀에 태움

코드

package implement;

import java.util.*;
import java.io.*;

public class BOJ_16639_괄호추가하기3 {
    /**
     * Expression 원소들을 저장
     */
    static class Expression{
        boolean number;
        long num;
        char exp;

        public Expression(boolean number, long num) {
            this.number = number;
            this.num = num;
        }

        public Expression(boolean number, char exp) {
            this.number = number;
            this.exp = exp;
        }
    }
    static long result = Long.MIN_VALUE;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        List<Expression> exp = new ArrayList<>();
        for(int i =0 ; i < N ; i++){
            if(0<=str.charAt(i)-'0'&&str.charAt(i)-'0'<10){     // 숫자 저장
                exp.add(new Expression(true, str.charAt(i)-'0'));
            } else{ // 연산자 저장
                exp.add(new Expression(false, str.charAt(i)));
            }
        }

        makeExpression(exp);
        
        System.out.println(result);
    }

    private static void makeExpression(List<Expression> rem) {
        if(rem.size() == 1){    // 숫자 하나만 남았을 때
            result = Math.max(result, rem.get(0).num);
            return;
        }
        for(int i =0 ; i < rem.size()-2 ; i+=2){  
            List<Expression> tmp = new ArrayList<>();
            for(Expression e:rem) tmp.add(e);
            long x = tmp.get(i).num;    // 숫자 1
            char y = tmp.get(i+1).exp;  // 연산자
            long z = tmp.get(i+2).num;  // 숫자 2
            tmp.remove(i+2);    // 리스트에서 없앰
            tmp.remove(i+1);
            tmp.remove(i);
            switch (y){
                case '+':{
                    long n = x+z;
                    tmp.add(i, new Expression(true, n));    // 기존 인덱스에 계산 값 추가
                    break;
                }
                case '-':{
                    long n = x-z;
                    tmp.add(i, new Expression(true, n));     // 기존 인덱스에 계산 값 추가
                    break;
                }
                case '*':{
                    long n = x*z;
                    tmp.add(i, new Expression(true, n));     // 기존 인덱스에 계산 값 추가
                    break;
                }
            }
            makeExpression(tmp);
        }
    }
}