[BOJ 10799] 쇠막대기

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

10799번: 쇠막대기

문제 분석

• 레이저가 없을때, 쇠막대기의 개수: 쇠막대기의 시작점 or 끝점
• 레이저 하나를 쏠때, 추가되는 쇠막대기의 개수 : 겹쳐져 있는 쇠막대기의 개수
• 계획:
• <stack>을 사용하여 '(', 쇠막대기의 시작점이 들어오면, count 해주고 동시에 stack에 push한다.
• '('과')'이 함께 들어오면 먼저 들어와 있던 '('을 pop해주고 기존에 들어있던 '('을 count한다.
• ')'이 들어오면 아무것도 하지 않는다.

stack<char>sticks;
string in;
int cnt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>in;
    for(int i=0;i<in.length();i++){
        if(in[i]=='('){//쇠막대기 시작
            sticks.push(in[i]);
            cnt++;
        }else {
            if(in[i - 1] == '(' && in[i] == ')'){//레이저
                sticks.pop();//레이저 시작점 pop
                cnt--;//레이저 시작점까지 센거 -1
                cnt = cnt + (int) sticks.size();
                //기존에 들어있던 쇠막대기 개수만큼 +
            }
            else sticks.pop();
            // 쇠막대기 끝났으면 pop
        }
    }
    cout<<cnt<<'\n';
    return 0;
}

느낀 점

• 보자마자 stack으로 풀면 되겠다는 생각이 들어 뿌듯하다.
• 처음에 이 논리로 풀었다가 레이저 시작점 센거를 빼주지 않아서 틀린 답이 나왔다.
• 그래서 쇠막대기가 끝날 때 세는 걸로 풀어도 봤다.
• 쇠막대기 시작일때 세는 것도 안될게 없는 거 같아 고쳐서 맞았습니다를 띄웠다.
• 쉬운 문젠데 문제를 읽기가 귀찮았다는 건 반성해야 겠다.

시간 복잡도

• push,pop -> O(1)
• 반복문 -> O(n)
  ☞ O(n)