[c++] 백준 10799 : 쇠막대기

[c++] 백준 10799 : 쇠막대기

---

 

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

10799번: 쇠막대기

 

접근

1. (은 막대가 하나씩 쌓인다고 생각한다. 스택에 값을 push한다.

2. )가 올 때, 스택 맨위에 (가 있을 경우에는 레이저로 취급된다. 이때 스택에 있는 (의 개수 만큼 막대 개수가 추가된다. size() 메서드를 이용한다.

3. 그냥 )가 오는 경우 막대 개수가 하나만 추가된다.

()레이저가 나타나면 스택에 push된 (의 개수만큼 막대 개수를 더하고 (하나를 pop한다. 스택상태: [(((]

()레이저가 한번 더 등장하므로 3+3 = 6개이다. (하나를 pop한다. 스택 상태: [(((]

 

레이저가 아닌 )의 경우 막대개수를 하나만 추가한다. 3+3+1=7 스택 상태: [((]

또한, 입력받은 문자열의 특정 인덱스에서 )가 나타날 때 그 앞 인덱스의 값이 (이라면 레이저이고, 아니면 막대인 경우로 구분해야 한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  string stick;
  int cnt = 0;

  getline(cin, stick);
  stack<int> S;
  for (int i = 0; i < stick.length(); i++) {  // 레이저의 경우
    if (stick[i] == ')' && stick[i-1] == '(') {
      S.pop();
      cnt += S.size();
    }
    else if (stick[i] == '(') { // 쇠막대기 쌓기
      S.push('(');
    }
    else {  // 막대 끝의 경우
      S.pop();
      cnt += 1;
    }
  }
  cout << cnt;
  return 0;
}