[Java] 백준 10799 쇠막대기

문제

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

10799번: 쇠막대기

풀이

문제가 '(' 와 ')' 기호 의 콤비내이션으로 이루어져있어 스택 알고리즘 으로 접근하는게 편하다 생각들었다.

 

문제를 해석하면  () 는 레이저 광선을 의미하고  (( .. )) 처럼 열림-닫힘 쌍이 아닌 것들은 쇠 막대기이다.

따라서 레이저가 한번 지잉 하면, 쇠막대기 개수만큼 정답 변수에 누적합을 하면 된다.

 

풀이 알고리즘은 다음과 같다.

1. 현재 기호가 ( 이면 stack +1 .
2. 현재 기호가 ) 이면 stack -=1  적용하고 다음과 같다.
   1. 현재 인덱스 i 에서 i-1 번째가 ( 기호이면 쇠막대기 만큼 더한다. 
   2. 현재 인덱스 i 에서 i-1번째가 ) 기호이면, 쇠막대기가 감소하는 것임으로 +1 을 한다.
3. 정답을 리턴한다.

 

 

코드

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

public class Main {
    BufferedWriter bw;

    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.solution();
    }
    public void solution() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        int stack =0;
        int ans =0;
        char[] charArr = str.toCharArray();
        for(int i =0  ;i < charArr.length; i++){
            if(charArr[i] == '(')
                stack++;
            else if(charArr[i] == ')'){
                stack--;
                if(charArr[i-1] == '('){
                    ans +=stack;
                }else{
                    ans ++;
                }
            }
        }
        bw.write(Integer.toString(ans));

        bw.close();
    }

}