JArchive 프로그래밍 일기

문제링크

스택을 이용해 풀었다. 

( ) 이렇게 레이저를 쏠 때 스택에 아무것도 없으면 막대 조각이 생성되지 않는다. 

괄호가 레이저를 쐈는지 식별하려면?

지금 문자열이  ) 이고, 이전이 ( 인지 확인하면 된다. 

 ( 는 막대가 시작하는 지점이다. 

( ( ) ) 길이 1의 막대에 레이저 1번 쏘면, 길이 1 + 현재 스택길이 1 ==> 총 조각 2개가 생성된다. 

( ( ( ) ) ) 길이 2의 막대에 레이저 1번 쏘면, 길이 2 + 현재 스택길이 2 ==> 총 4개가 생성된다. 

) 는 막대가 끝나는 지점이니까 answer 에 +1을 한다. 

맞았습니다 코드링크

/** 쇠막대기
 https://www.acmicpc.net/problem/10799
 http://boj.kr/4fcfe35ad9a14a5898bf22af9c5f25c9
 */

#include <bits/stdc++.h>
using namespace std;

long long answer;
string input;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> input;

  stack<char> st;
  int len = input.length();
  for(int i = 0; i < len; i++){

    if(input[i] == '(') {
      st.push(input['i']);
    }
    else if(input[i-1] == '(' && input[i] == ')'){ // 레이저
      st.pop();
      answer += st.size();
    }else { // 막대의 마지막 꼬다리
      answer++;
      st.pop();
    }
  }

  cout << answer;
  return 0;
}