16638 - 괄호 추가하기 2

info

• 문제 보기: 16638 - 괄호 추가하기 2
• 소요 시간: 💥1시간 초과
• 풀이 언어: java
• 체감 난이도: 4️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

구현 비트마스킹

풀이 코드

info

• 메모리: 14516 KB
• 시간: 120 ms

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

public class Main {
    static int n;
    static String eq;
    static long ans = Long.MIN_VALUE;
    
    public static void main(String[] args) throws IOException {
        input();
        
        for (int bit = 0; bit < (1 << n); ++bit) {
            if ((bit & (bit << 1)) != 0) continue; // check if overlapping

            List<Character> charList = eq.chars().mapToObj(i->(char)i).collect(Collectors.toList());

            // insert in reverse order to keep index
            for (int i = n-1; i > -1; --i) {
                if ((bit & (1 << i)) != 0) { // if insertion position found
                    int ldx = i * 2;
                    int rdx = i * 2 + 3;
                    charList.add(rdx, ')');
                    charList.add(ldx, '(');
                }
            }

            StringBuilder expr = new StringBuilder();
            for (char ch : charList) {
                expr.append(ch);
            }
            long val = eval(expr.toString());
            ans = ans < val ? val : ans;
        }

        System.out.println(ans);
    }

    // calculate expression
    public static long eval(String expr) {
        Deque<Long> numQ = new ArrayDeque<>();
        Deque<Character> opQ = new ArrayDeque<>();
        
        int i = 0;
        while (i < expr.length()) {
            char ch = expr.charAt(i);
            
            if (Character.isDigit(ch)) { // if 0 ~ 9
                long num = 0;
                while (i < expr.length() && Character.isDigit(expr.charAt(i))) {
                    num = num*10 + (expr.charAt(i++)-'0');
                }
                numQ.push(num);
                continue;
            }
            else if (ch == '(') {
                opQ.push(ch);
            }
            else if (ch == ')') {
                while (opQ.peek() != '(') {
                    numQ.push(calc(opQ.pop(), numQ.pop(), numQ.pop()));
                }
                opQ.pop(); // remove '('
            }
            else if (ch == '+' || ch == '-' || ch == '*') {
                while (!opQ.isEmpty() && precedence(ch) <= precedence(opQ.peek())) {
                    numQ.push(calc(opQ.pop(), numQ.pop(), numQ.pop()));
                }
                opQ.push(ch);
            }
            
            ++i;
        }

        while (!opQ.isEmpty()) {
            numQ.push(calc(opQ.pop(), numQ.pop(), numQ.pop()));
        }

        return numQ.pop();
    }

    public static long calc(char op, long b, long a) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
        }
        return 0;
    }

    public static int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*') return 2;
        return 0;
    }
    
    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        n >>= 1; // number of operators
        eq = br.readLine();
    }
}

풀이 해설

WIP

메모

• 아이디어도 필요하고 약간의 CS 지식도 요구하는, 난이도 있는 문제
• 자바도 파이썬처럼 성능 이슈로 Stack 대신 Deque 쓰는 것이 좋음.