[백준/JAVA] 쇠막대기

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

---

- 문제 풀이

(https://steady-coding.tistory.com/10 님 문제 풀이 참고)

 

스택 알고리즘 사용

• 여는 괄호가 나올 때마다 스택에 추가합니다. 이는 쇠막대기의 시작을 의미하므로 각 막대기가 어디서 시작했는지 기록하는 용도입니다.
• 닫는 괄호가 나올 때 처리 방식은 두 가지입니다:
  • 바로 이전 문자가 '('이면, 이는 레이저를 의미합니다. 현재 스택에 있는 쇠막대기 수만큼 조각이 추가됩니다. ( 괄호가 닫히기전에 레이저를 쏘면 남은 '(' 만큼 갯수가 늘어남)
  • 이전 문자가 ')'이면, 이는 막대기의 끝을 의미하므로 막대기가 하나 끝났고 조각이 하나 추가됩니다. ( 사진을 보면 ')'가 연속해 있으면 단순히 막대기만 하나더 들어옴)

 

 

1. '('을 만났을 때

  ➜ stack에 '('을 push한다

2. ')'을 만났을 때

  ➜ stack에서 pop한다

    2-1. ')' 바로 전 문자가 '('일 때

          ➜  레이저이므로 stack 사이즈만큼 더해준다!

    2-2. ')' 바로 전 문자가 ')'일 때

          ➜  그냥 1만 더해준다!

 

 

- 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        Stack<Character> stack = new Stack<>();
        int answer = 0;

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                stack.push('(');
            }else { // s.charAt(i) == ')'
                stack.pop();
                if(s.charAt(i-1) == '(') { // 레이저를 의미
                    answer += stack.size();
                }else{ // ')'
                    answer += 1;
                }
            }
        }
        System.out.println(answer);
    }
}