[Algorithm] 쇠막대기

이번 문제는 stack을 이용한 문제다. 괄호로 표현된 문자열에서 절단기와 막대기 두종류가

있는데 절단되는 막대기의 갯수를 구하는 문제다. 해결방법은 다음과 같다.

'(' 기호가 들어오면 스택에 해당 인덱스를 저장한다. ')'기호가 들어오면 스택에서 pop을

통해 인덱스를 얻어 온 후 바로 인접한 인덱스면 절단기라고 판단하고 여태 까지 저장된

막대기들을 절단한다. 절단 하면서 얻어지는 결과값을 더해준다.

예를 들어 , 두번째 절단기가 나타나기 전까지 stack에 들어있는 '('는 4개이다. ')'를 만나고

pop을 했을 때 인접한 인덱스이므로 절단기로 판단하고 나머지 3개에 대해 cutting을 하게

되면 3개의 조각이 추가된다. 만약 절단기가 나타나지 않고 ')'를 만나면 +1을 해준다.

Source:
import java.io.*;
import java.util.*;
public class a_10799 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder(br.readLine());
int len = sb.length();
Stack<Integer> stk = new Stack();
char temp;
int p;
int ans=0;
for(int i=0;i<len;i++){
temp = sb.charAt(i);
if(temp=='(') stk.push(i);
else{
p=stk.pop();
if(i-p==1) ans+=stk.size();
else ans++;
}
}
System.out.println(ans);
}
}