문제

Example Input/Output

// IN
// (): 레이저 (쇠막대기를 자를 수 있는)
// (: 쇠막대기 시작 (왼쪽 끝)
// ): 쇠막대기 끝 (오른쪽 끝)
()(((()())(())()))(())

// OUT
17 // 쇠막대기 조각 수

C++ 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int pipeCount = 0;

    int score = 0;
    bool lastOpen = false;
    for (auto c: s)
    {
        if (c == '(')
        {
            score++;
            lastOpen = true;
        }
        else
        {
            score--;
            pipeCount += lastOpen ? score: 1;
            lastOpen = false;
        }
    }

    cout << pipeCount;
}

메모

1. 문자열에서 레이저 표시
   

2. 문자열에서 쇠막대기 표시
   

3. 레이저 지이잉
   

4. 레이저가 쇠막대기를 자르는 위치 표시

   • 닫는 괄호가 나올 때 쇠막대기가 잘리는 것을 확인할 수있다

5. 또 다른 정보를 표시, 여는 괄호라면 스택 +1, 닫는 괄호라면 스택 -1
   

6. 1~5번을 통해 규칙 찾기

   • 레이저에 포함된 닫는 괄호라면, 현재 스택만큼 쇠막대기가 잘린다
   • 쇠막대기에 포함된 닫는 괄호라면, 쇠막대기가 1번 잘린다

7. 코드로 옮기기

   • 전제: 모든 문자열은 균형잡힌 괄호 문자열이다
   1. 각 문자에 대해 (for)
   2. 문자가 (면 점수 +1
   3. 문자가 )면
      • 일단 점수 -1
      • 만약 이전 문자가 (였다면 쇠막대기 += 현재 점수
      • 아니라면 쇠막대기 += 1

• 원래 스택을 써서 풀었는데, 어차피 균형잡힌 문자열이라 굳이 스택을 쓰지 않아도 된다.