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

걸린 시간: 12m10s

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

문제 접근 방법

스택을 완전히 구현할 필요는 없고, 배열과 인덱스를 사용해서 스택과 같이 사용했다. push와 pop의 경우는 인덱스를 각각 +1/-1 하여 스택의 push/pop과 같이 작동하도록 했다.

명령을 구분하는 방법으로는 입력을 문자열로 받고 첫 번째 글자('p', 's', 'e', 't')로 구분했고 이를 switch문을 이용해서 각 명령의 해당하는 연산을 했다. 'p'같은 경우는 두 가지가 있기 때문에 따로 두 번째 문자('u', 'o')를 확인했다.

C++ 코드

1#include <bits/stdc++.h>
2using namespace std;
3
4#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
5
6int i;
7int arr[10001];
8
9int main() {
10  char str[6];
11  int n;
12  scanf("%d", &n);
13
14  while(n--) {
15    scanf("%s", str);
16
17    switch(str[0]) {
18      case 'p': 
19        {
20          if(str[1] == 'u') {
21            int v; scanf("%d", &v);
22            arr[i] = v;
23            ++i;
24          } else {
25            if(i > 0) {
26              --i;
27              printf("%d\n", arr[i]);
28            } else {
29              cout << -1 << endl;
30            }
31          }
32          break;
33        }
34      case 't': { printf("%d\n", i==0 ? -1 : arr[i-1]); break; }
35      case 's': { printf("%d\n", i); break; }
36      case 'e': { printf("%d\n", i==0); break;}
37    }
38  }
39  return 0;
40}

시간 복잡도

• n개의 명령을 입력받음 - O(N)
• 명령(문자열)의 첫 번째 문자를 확인하는 연산 - if문 - O(1)
• push, pop, size, empty, top 연산 - O(1)
• 최종 시간 복잡도: O(N)

공간 복잡도

• n개의 입력이 주어지고 모든 명령이 push일 경우 - O(N)
• 최종 공간 복잡도: O(N)