백준 10799 쇠막대기 자바[java]

• 쇠막대기

10799번: 쇠막대기

 

[문제 간단 설명]

(()())((()())) 입력이 이런식으로 주어진다.

이 입력에는 레이저와 쇠막대기에 대한 내용이 포함되어있다.

레이저는 () 열자마자 바로 닫히는 괄호.

쇠막대기는 그 외의 괄호들.

레이저가 쇠막대기를 자를때,

남은 쇠막대기들의 개수를 구하는 문제다.

 

 

고민하다가 도저히 어떻게 구현해야할지 모르겠어서

다른 사람의 풀이를 참고했다.

 

 

[풀이]

Stack을 이용.

'(' 는 스택에 추가.

')' 는 스택에서 하나 제거하고, 두가지 경우가 존재.

case 1ㅣ      ')' 전에 나온 문자가 '(' 인 경우

   -> result += 스택의 크기.

case 2 ㅣ     ')' 전에 나온 문자가 ')' 인 경우

    -> result += 1

 

case 1은 레이저를 의미한다.

레이저가 자르면,

막대기들의 갯수만큼 새로운 막대기들이 생긴다.

스택의 크기가 현재 있는 막대기들의 갯수이므로

result += 스택의 크기.

 

case 2는 막대기의 끝을 의미한다.

이미 레이저에 의해 잘린 막대기들의 갯수는 구했다.

막대기 끝에는 잘리고 남은 나머지 하나가 있을 것이므로

result += 1

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> stk = new Stack();
        int result = 0;
        String str = sc.next();
 
        for(int i =0; i < str.length(); i++){
            char oneChar = str.charAt(i);
 
            if(oneChar == '(')
                stk.push(oneChar);
            else{
                stk.pop();
                if(str.charAt(i-1) == '(')  result += stk.size();
                else result += 1;
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
}