[백준 BOJ][stack] 10799 쇠막대기

10799_쇠막대기

링크

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

 

풀이

 

이 문제는 Stack을 사용해서 풀 수 있습니다.

 

일단 쇠막대기의 오른쪽 끝과 레이저를 구분해서 두 가지의 경우로 나누어 풀면 됩니다.

 

여는 괄호가 들어온다면 스택에 push하고 닫는 괄호가 들어온다면 pop을 해줍니다.

닫는 괄호가 들어왔을 때는 전의 괄호가 여는 괄호인지 닫는 괄호인지 확인합니다.

여는 괄호라면 레이저이기 때문에, 현재 쇠막대기만큼 즉, stack의 size만큼 더해주면 됩니다.

닫는 괄호라면 쇠막대기의 오른쪽 끝이기 때문에, 1을 더해주면 됩니다.

 

 

두 번째 예제를 실제로 그려서 계산해보면 이렇게 됩니다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

//10799_쇠막대기 #include <iostream> #include <string> #include <stack> using namespace std;   int main() {     ios_base::sync_with_stdio(false); cin.tie(NULL);       string str;     stack<int> stk;     int result = 0;     char before;       cin >> str;       for (auto c : str) {         if (c == '(')             stk.push(1);           else {             stk.pop();               if (before == '(') result += stk.size();    //레이저일 때, stack의 size만큼 더해줌             else result++;                                //쇠막대기의 오른쪽 끝일 때, 1을 더해줌         }           before = c;     }       cout << result << "\n";       return 0; } Colored by Color Scripter

cs