[백준] 10845번: 큐 (직접 구현과 비교, c++)

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

큐 자료구조를 구현하는 문제인데, C++의 STL 라이브러리 <queue>를 이용해도 되지만, 직접 구현해보고 속도를 비교해보았다.

방법 1: 직접 구현

일반 큐 혹은 원형 큐로 구현하는 선택지가 있었다.

 

명령어가 N개라면 배열의 크기를 N개로 설정하면 되니 구현이 더 쉬운 일반 큐 방법을 선택했다.

#include <iostream>
#include <string>

class Queue {
private:
  int *queue;
  short front = 0, back = 0;

public:
  Queue(short max_size) {
    queue = new int[max_size];
  }

  short get_size() {
    return back - front;
  }

  bool is_empty() {
    return (get_size() == 0);
  }

  void push(int x) {
    queue[back] = x;
    back++;
  }

  int pop() {
    int result;
    if (is_empty()) {
      return -1;
    }
    return queue[front++];
  }

  int get_front() {
    if (is_empty()) {
      return -1;
    }
    return queue[front];
  }

  int get_back() {
    if (is_empty()) {
      return -1;
    }
    return queue[back - 1];
  }
};


int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  short N;
  int value;
  std::string command;

  std::cin >> N;
  Queue q(N);

  for (short i = 0; i < N; i++) {
    std::cin >> command;
    if (command == "push") {
      std::cin >> value;
      q.push(value);
    }
    else if (command == "pop") {
      std::cout << q.pop() << '\n';
    }
    else if (command == "size") {
      std::cout << q.get_size() << '\n';
    }
    else if (command == "empty") {
      std::cout << q.is_empty() << '\n';
    }
    else if (command == "front") {
      std::cout << q.get_front() << '\n';
    }
    else if (command == "back") {
      std::cout << q.get_back() << '\n';
    }
  }

  return 0;
}

방법 2: STL 사용

main 함수는 거의 같으나, <queue>의 사용법을 따른다.

#include <iostream>
#include <queue>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  short N;
  int value;
  std::string command;
  std::queue<int> q;

  std::cin >> N;
  for (short i = 0; i < N; i++) {
    std::cin >> command;
    if (command == "push") {
      std::cin >> value;
      q.push(value);
    }
    else if (command == "pop") {
      if (q.empty()) {
        value = -1;
      }
      else {
        value = q.front();
        q.pop();
      }
      std::cout << value << '\n';
    }
    else if (command == "size") {
      std::cout << q.size() << '\n';
    }
    else if (command == "empty") {
      std::cout << q.empty() << '\n';
    }
    else if (command == "front") {
      if (q.empty()) {
        value = -1;
      }
      else {
        value = q.front();
      }
      std::cout << value << '\n';
    }
    else if (command == "back") {
      if (q.empty()) {
        value = -1;
      }
      else {
        value = q.back();
      }
      std::cout << value << '\n';
    }
  }

  return 0;
}

 

비교

 

위가 방법 2, 아래가 방법 1이다.

 

메모리 사용량은 같은데, 코드를 짜는건 1번이 훨씬 오래 걸렸다. (디버깅 하는데에도 10분 넘게 걸렸다..)

 

STL이 충분히 효율적이라는 것을 알았으니, 앞으로는 편하게 queue를 써야겠다!