10845. 큐

https://www.acmicpc.net/problem/10845 | https://www.acmicpc.net/problem/18258

걸린 시간: 23m36s

문제

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

명령은 총 여섯 가지이다.

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

문제 접근 방법

큐를 구현하면 된다. 각 명령어를 입력받고 앞의 한 글자만 확인해서 해당 명령들의 로직을 실행하도록 했다.

처음에는 배열을 사용해서 간단히 큐를 시뮬레이션 하려고 했으나 앞에서 삭제를 해야하는 것 때문에 문제가 있었다.

시도 1 - 실패

front와 back을 아래와 같이 선언 한 다음,

1int front = 0;
2int back = 0;

pop을 할때마다 ++front 해서 시작점을 앞으로 한 칸씩 밀려고 했다.

1int main(){
2  // ...
3  while(n--) {
4    scanf("%s", command);
5    char ch = command[0];
6    if(ch == 'p') {
7      if(command[1] == 'u') {
8        int x;
9        cin >> x;
10        q[size] = x;
11        ++size;
12        ++back;
13      } else {
14        if(size==0) {
15          printf("-1\n");
16          front = back = 0;
17        } else {
18          printf("%d\n", q[front]);
19          ++front;
20          if(front == back) front = back = 0;
21          --size;
22        }
23      }
24    } else if(ch == 's') {
25      printf("%d\n", size);
26    } else if(ch == 'e') {
27      printf("%d\n", size==0);
28    } else if(ch == 'f') {
29      printf("%d\n", (size==0) ? -1 : q[front]);
30    } else if(ch == 'b') {
31      printf("%d\n", (size==0) ? -1 : q[back-1]);
32    }
33  }
34  return 0;
35}

하지만 생각대로 동작하지 않았다... STL queue도 있으나 이는 반칙이고.. 그래서 진짜 구현을 해야하나 하다가, 연결리스트를 사용하는 쪽으로 갔다.

시도 2 - 성공

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  ios; 
8  int n;
9  scanf("%d", &n);
10  list<int> q;
11  while(n--) {
12    char command[6];
13    scanf("%s", command);
14    char ch = command[0];
15    if(ch == 'p') {
16      int v; scanf("%d", &v);
17      if(command[1] == 'u') {
18        q.insert(q.end(), v);
19      } else {
20        if(q.size()==0) {
21          printf("-1\n");
22        } else {
23          printf("%d\n", q.front());
24          q.pop_front();
25        }
26      }
27    } else if(ch == 's') {
28      printf("%lu\n", q.size());
29    } else if(ch == 'e') {
30      printf("%d\n", q.size() == 0);
31    } else if(ch == 'f') {
32      printf("%d\n", (q.size() == 0) ? -1 : q.front());
33    } else if(ch == 'b') {
34      printf("%d\n", (q.size() == 0) ? -1 : q.back());
35    }
36  }
37  return 0;
38}
39

시간 복잡도

n개의 명령어를 살행 - O(N)
연결리스트의 insert - O(1) (linear in number elements inserted and only 1 element is added, hence O(1))
최종 시간 복잡도: O(N)

공간 복잡도

n개의 명령이 전부 push일 경우 연결리스트의 크기 - O(N)
최종 공간 복잡도: O(N)