[BOJ10799] 쇠막대기 (스택, 자료구조)

 

 

---

문제 링크 

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

10799번: 쇠막대기

 

문제 풀이 

- 스택 자료 구조 응용 문제 

- 시간 복잡도 : O(N)

 

절차

1) 스택 선언하고 "(" 인 경우 스택에 추가한다.

2) ")"는 괄호일 때

2-1) 이전 괄호가 "(" 인 경우 레이저가 되므로, pop() 후 stack.size() 를 결과에 합산한다. 

2-2) 레이저가 아닌 경우(=쇠막대 하나가 끝나는 위치) pop() 후 +1 을 결과에 합산한다.

 

예제입력 2 
(((()(()()))(())()))(()())

예제출력 2
24

3 + 4 + 4 + 1 + 1 + 3 + 1 + 2 + 1 + 1 + 3 = 24

 

 

제출 코드

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

public class Main {
    
    static String input;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine(); // 입력

        Stack<String> stack = new Stack();
        String[] parentheses = input.split("");

       int result = 0;
        String prev = "";
        for(String p : parentheses) {
            if("(".equals(p)) {
                stack.push(p);
                prev = p;
            } else { 
                stack.pop();

                if("(".equals(prev)) result += stack.size(); // 레이저인 경우
                else result += 1; // 쇠막대 하나가 끝나는 위치인 경우

                prev = p;
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(result + "");
        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    
}