👨‍💻 문제

---

✍️ 풀이

⚗️ 쓸모없는 정보를 쓸모있는 정보로

해당 문제가 요구하는 것은 문자열의 내용이 아닌 문자열의 길이이다.
그렇기에 문자열을 길이로 다루면 편리하게 문제를 풀 수 있을 것이다.

K(Q)는 Q라는 문자열을 K번 반복한다.
Q를 숫자로 저장한다면, K(Q)는 K*Q가 될 것이고 이 또한 숫자가 된다.

해당 문제에서 K를 제외한 숫자들(Q)은 모두 문자열이다.
우리가 필요한 것은 문자열의 길이이기 때문에 어떤 문자인지는 알 필요가 없다.

그렇기에 K를 제외한 모든 숫자를 1로 바꿔버린다.
여기서 1은 해당 문자열의 길이를 의미한다.

    public static void main(String[] args) throws IOException {

        int[] values = inputValues();
        replaceStringToLength(values);
        
        ...
        
    }

    // K와 괄호를 제외한 숫자를 모두 1(문자열의 길이)로 변경
    private static void replaceStringToLength(int[] values) {
        for (int i = 0; i < values.length; i++) {
            // 괄호
            if (values[i] == OPENER || values[i] == CLOSER) {
                continue;
            }
            // K
            if (i + 1 < values.length && values[i + 1] == OPENER) {
                continue;
            }
            values[i] = 1;
        }
    }

input :
33(562(71(9)))

가공 전 : 
[3, 3, (, 5, 6, 2, (, 7, 1, (, 9, ), ), )]

가공 후 : 
[1, 3, (, 1, 1, 2, (, 1, 1, (, 1, ), ), )]

📚️ 스택 압축

이제 스택을 활용하여 K(Q)를 수행하도록 한다.

아래 규칙을 따라 스택을 압축한다.
구현을 시작하기 전에 이러한 규칙을 먼저 잘 생각하는 것이 가장 중요한 것 같다.

1. )가 나오기 전까지 모두 스택에 넣는다.
2. )가 나온다면 (까지 스택에서 뺀다.
3. 괄호 안의 숫자들의 합이 Q가 된다.
4. 숫자를 하나 더 뺀다 (K).
5. Q*K를 다시 스택에 집어넣는다.

    public static void main(String[] args) throws IOException {
    
    	...

        for (int value : values) {
            if (value == CLOSER) {
                compress();
            }
            else {
                stack.push(value);
            }
        }
        
        ...
    }
    
    private static void compress() {

        int Q = 0;

        for (int value = stack.pop(); value != OPENER; value = stack.pop()) {
            Q += value;
        }

        int K = stack.pop();

        stack.push(K * Q);
    }

🖨️ 출력

이상의 압축을 마치게 되면
스택에는 몇 개의 숫자들이 남게될 것이다.
해당 숫자들은 모두 문자열들의 길이로,
해당 숫자들의 합이 모든 문자열의 길이가 된다.

        System.out.println(stack.stream().mapToInt(Integer::valueOf).sum());

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {

    // 변경하는 이유 : 문자열의 길이가 괄호의 아스키코드와 같아질 수 있기 때문
    private static final int OPENER = -1;
    private static final int CLOSER = -2;

    private static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) throws IOException {

        int[] values = inputValues();
//        System.out.println("가공 전 : \n"+Arrays.stream(values).mapToObj(_1662::getStringValue).toList() + '\n');

        replaceStringToLength(values);
//        System.out.println("가공 후 : \n"+Arrays.stream(values).mapToObj(_1662::getStringValue).toList() + '\n');

        for (int value : values) {
//            System.out.println(stack.stream().map(_1662::getStringValue).toList() + "  <-  " + getStringValue(value));
            if (value == CLOSER) {
                compress();
            }
            else {
                stack.push(value);
            }
        }

        System.out.println(stack.stream().mapToInt(Integer::valueOf).sum());

    }

    private static int[] inputValues() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        return Arrays.stream(str.split("")).mapToInt(value -> {
            if (value.equals("(")) {
                return OPENER;
            }
            if (value.equals(")")) {
                return CLOSER;
            }
            return Integer.parseInt(value);
        }).toArray();
    }

    // K와 괄호를 제외한 숫자를 모두 1(문자열의 길이)로 변경
    private static void replaceStringToLength(int[] values) {
        for (int i = 0; i < values.length; i++) {
            // 괄호
            if (values[i] == OPENER || values[i] == CLOSER) {
                continue;
            }
            // K
            if (i + 1 < values.length && values[i + 1] == OPENER) {
                continue;
            }
            values[i] = 1;
        }
    }

    private static void compress() {

        int Q = 0;

        for (int value = stack.pop(); value != OPENER; value = stack.pop()) {
            Q += value;
        }

        int K = stack.pop();

        stack.push(K * Q);
    }

    // log
    private static String getStringValue(int value) {
        return value == OPENER ? "(" : value == CLOSER ? ")" : String.valueOf(value);
    }

}