백준 10799-쇠막대기 [Java]

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

10799번: 쇠막대기

초기 코드(시간 초과)

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

class Main {
    public static void main(String[] args) throws IOException {
        int answer = 0;
        Stack<Character> stick = new Stack<>();
        Stack<Integer> laser = new Stack<>();

        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        String input = br.readLine();

        char recent = 0;

        for (int i = 0; i < input.length(); i++) {
            char current = input.charAt(i);
            if (current == '(') {
                //laser
                if (i < input.length() - 1 && input.charAt(i + 1) == ')') {
                    recent = current;
                    continue;
                }
                stick.push(current);
                laser.add(1);
                recent = current;
                continue;
            }
            //laser
            if (recent == '(') {
                if (!laser.isEmpty()) {
                    laser.replaceAll(e -> e + 1);
                    recent = current;
                }
                continue;
            }
            stick.pop();
            answer += laser.remove(laser.size() - 1);
            recent = current;
        }

        System.out.println(answer);
    }
}

 

새로 알게된 점 

List.replaceAll() : list의 모든 요소를 특정값으로 대체함. (Stack은 List를 구현한 Vector를 상속받았기 때문에 사용가능)

정답 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        int answer=0;
        Stack<Character> st = new Stack<>();
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        
        for(int i=0; i<input.length(); i++){
            char current = input.charAt(i);
            if(current=='('){
                st.push(current);
                continue;
            }
            
            st.pop();
            //laser
            if(input.charAt(i-1)=='('){
                answer+=st.size();
                continue;
            }
            answer++;
        }

        System.out.println(answer);
    }
}

'('이 나오면 무조건 push

')'나오면 pop(), 이전 문자가 '('일 때는 레이저이므로 stack의 만큼 cnt(레이저 왼쪽은 막대의 개수만큼의 조각이 생긴다). 아닐 땐 +1 해준다. 막대 하나당 레이저가 한번은 쏘여지기 때문에 레이저 다음 막대가 끝나는 시점엔 조각하나만 남기 때문