1079 - 쇠 막대기 (Java)

 

---

 

문제

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

 

풀이

괄호만 보면 스택먼저 생각나는 만큼, 스택을 활용해서 풀면 된다.

 

여는 괄호는 현재 막대기의 개수를 의미한다.

 

그러다가 이제 닫는 괄호가 나오면, 레이저를 의미한다.

 

이때 스택에서 여는괄호 하나를 꺼내서 닫는 괄호와 쌍을 맞추어 레이저가 구성된다.

 

그러면 막대들이 절단될것이고, 3개의 막대들이 있다고 가정 하면 3개가 잘려나갈것이다.

 

단, 앞서 레이저였는데 (닫는 괄호가 나왔는데) 또 닫는 괄호가 나온다면 이는 막대의 끝을 의미한다.

막대의 끝을 만나면 1개를 추가해줌으로 레이저로 인해 잘린 오른쪽 값을 체크할 수 있다.

 

 

 

코드

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

public class Main {

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<String> bar = new ArrayList<>(Arrays.asList(br.readLine().split("")));
        Stack<String> st = new Stack<>();
        int answer = 0;

        for (int i=0; i<bar.size(); i++) {
            String val = bar.get(i);

            if(st.isEmpty() || val.equals("(")){
                st.push(val);
                continue;
            }

            // 앞에 값도 닫는 값이면 1만 더한다.
            if(bar.get(i-1).equals(")")){
                answer++;
                st.pop();
                continue;
            }
            st.pop();
            answer += st.size();
        }
        
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기