쇠막대기 - Stack

Stack을 활용한 문제이다(괄호문제가 나온다면 stack을 고려해보자)

괄호안에서 쇠막대기와 레이져를 구분을 해야 문제를 해결하는게 팁이다.

주어진 문제에 예시 이미지를 보면 레이져의 경우 닫힌괄호( " ) " )가 나오면 바로 직전 문자의 경우가 열린 괄호가 나온다

( " ( " ) 

또한 레이져가 한번 실행되면 나무막대가 잘리면서 좌측의 나무막대의 갯수가 나오는데 해당 내용을 활용하여 답을 구하면 된다

마지막으로 쇠막대기의 끝 부분 닫힌 괄호를 만나면 해당 괄호에 해당하는 열린괄호를 pop해주면된다

 

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static int solution(String str){
        int answer =0;

        Stack<Character> st = new Stack<>();

        char[] c = str.toCharArray();
        for(int i=0; i<str.length(); i++){
            if(c[i]=='('){ //열린괄호를 만나면 push 해준다
                st.push(c[i]);
            }else {
               st.pop(); //레이져와 쇠막대기 상관없이  stack에서 끄내준다 닫힌괄호와 매핑되는 
                        // 열린괄호를 stack에서 없애야 잘린막대기의 수를 구할수있다
               if(c[i-1]=='('){ //레이져인경우
                   answer+=st.size(); //레이져인경우 쇠막대기가 잘렸으모로 남은 스택의 사이즈만큼 더해주면된다
               }else {
                   answer++;
               }
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        System.out.println(solution(str));
    }
}

결과
17