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

걸린 시간: 29m38s

문제

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

문제 접근 방법

1. 열린 괄호는 스택에 push
2. 닫힌 괄호가 나오면 현재 스택의 size만큼을 count에 추가한다 (스틱의 개수이기 때문에..)
   1. 단 ()와 같이 레이저인 경우가 아니라 (())와 같이 레이저 이후 연속된 닫힌 괄호의 경우는 그냥 count + 1

아래는 대충 고뇌의 흔적...

C++ 코드

1#include <bits/stdc++.h> 
2using namespace std;
3
4#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
5
6int main() {
7  stack<char> stk;
8  string s;
9  cin >> s;
10  int sticks = 0;
11
12  bool opened = false;
13
14  for(char c : s) {
15    if(c == '(') {
16      opened = true;
17      stk.push(c);
18    } else if (c == ')') {
19      stk.pop();
20      if(opened) {
21        opened = false;
22        sticks += stk.size();
23      } else {
24        ++sticks;
25      }
26    }
27  }
28
29  cout << sticks << endl;
30
31  return 0;
32}

시간 복잡도

• 입력된 문자열의 길이 만큼 순회 - O(S), S = 문자열 길이
• 열린 괄호와 닫힌 괄호의 확인 작업 - 단순 if문 - O(1)
• 스택의 push/pop - O(1)
• 최종 시간 복잡도: O(S)

공간 복잡도

• 주어진 문자열의 길이가 S라고 했을 때, 최악의 경우 문자열의 반이 열린 괄호일 수 있다 - (((()))) - O(S/2)
• 최종 공간 복잡도: O(S)