문제 1662번

소스코드

import java.io.*;
import java.util.*;
public class boj1662 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = br.readLine().toCharArray();
        Stack<Integer> mul = new Stack<>();
        Stack<Integer> len = new Stack<>();
        int cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == '('){
                cnt-= 1;
                int mulnum = arr[i-1] - '0';
                len.add(cnt);
                mul.add(mulnum);
                cnt =0;
            }else if(arr[i] == ')'){
                int val = mul.pop();
                val *= cnt;
                int plus = len.pop();
                cnt = plus + val;
            }else cnt++;
        }
        System.out.println(cnt);
    }
}

풀이 접근

1. 처음에는 입력 값을 뒤에서 부터 index 값을 통해서 해결하려 했지만, 예외 케이스도 있는지 틀렸다는 정답을 받았다.
2. 그 다음으로는 곱셈을 위한 stack 하나, 곱셈 할 대상이 되는 길이(len) stack 하나를 통해 문제를 해결했다.
3. 입력을 캐릭터 배열로 만들고, 앞에서 부터 탐색에 들어간다. 4. 해당 값이 '('가 나온다면 이전 값을 mul에 넣고 지금까지의 cnt값(덧셈의 길이)에서 하나 제외하고 len 값에 넣는다
4. ')'가 나온다면 이번 괄호의 len 값인 cnt에 mul에서 pop한 값을 곱해주고, 그 다음 괄호 안의 내용인 len값을 plus 변수에 넣어 cnt변수에 plus랑 곱한 값을 더해서 저장한다.
5. 4~5번 과정이 아니라면 덧셈 할 인덱스의 숫자이기 때문에 cnt를 증가 시켜준다.

문제 핵심

• 만약 자료구조를 사용하는 것이 아닌, 배열로 풀었으면, 예외 케이스가 있었을 것이다! (사실 뭔지 아직도 모르겠다.)
• 뭔가 복잡하긴 하지만 로직을 짤 수 있는지가 문제의 핵심인 것 같다.