[C++]백준 - 18258번 문제

18258번: 큐 2 (acmicpc.net)

18258번: 큐 2

 

18258번 : 큐 2

---

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

명령은 총 여섯 가지이다.

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

 

입력

---

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

 

출력

---

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

---

 

생각해 볼 점

---

시간 제한이 길지 않은 관계로 최대한 간결하게 만들어야합니다.

 

명령의 수가 2000000 이하이므로, push만 한다는 가정을 해도 큐의 공간은 2000000을 넘지 않을 것입니다.

 

따라서, 고정 길이 2000000을 가진 int 배열로 구현하려 합니다.

 

원칙적으로는 동적 할당을 이용하거나, Linked List 등을 이용하는 게 옳지만, 편의상 입력 값에 맞춘 고정 배열을 사용하겠습니다.

 

큐는 FIFO 구조를 가진 자료구조이므로, Front와 Back을 가진 클래스 형태로 구현하려 합니다.

 

push와 pop이 반복되어 Front와 Back의 값이 배열의 끝에 다다르면, 다시 0으로 초기화해주는 것이 원칙입니다. 그러나, 입력값을 보았을 때 배열의 끝을 넘어가는 일은 없을 것이므로 구현하지 않겠습니다.

 

명령어의 종류는 push, pop, size, empty, front, back이므로, 명령어의 두번 째 자리 알파벳이 모두 다릅니다. 따라서, 명령어를 받았을 때 두번 째 자리를 보고 어떤 명령어인지 판단하도록 합니다.

 

코드

---

 

#include <iostream>
#include <string>
using namespace std;

class Queue
{
private:
    int q[2000000] = {0,};
    int f;
    int b;
public:
    Queue();
    void push(int n);
    int pop();
    int size();
    int empty();
    int front();
    int back();
};

Queue::Queue()
{
    f = 0;
    b = -1;
}

void Queue::push(int n)
{
    q[++b] = n;
}

int Queue::pop()
{
    if(empty()) return -1;
    return q[f++];
}

int Queue::size()
{
    return b - f + 1;
}

int Queue::empty()
{
    if(f > b) return 1;
    else return 0;
}

int Queue::front()
{
    if(empty()) return -1;
    return q[f];
}

int Queue::back()
{
    if(empty()) return -1;
    return q[b];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int N;
	cin >> N;
	Queue q = Queue();
	for(int i = 0; i < N; i++)
	{
	    string input;
	    cin >> input;
	    
	    switch(input[1])	//명령어의 2번 째 char를 보고 판단함
	    {
	        case 'u':
	            int n;
	            cin >> n;
	            q.push(n);
	            break;
	        case 'o':
	            cout << q.pop() << "\n";
	            break;
            case 'i':
                cout << q.size() << "\n";
                break;
            case 'm':
                cout << q.empty() << "\n";
                break;
            case 'r':
                cout << q.front() << "\n";
                break;
            case 'a':
                cout << q.back() << "\n";
                break;
	    }
	}
	
	return 0;
}

 

 

그 외

---

cin.tie(NULL)을 쓰지 않으면 시간 초과가 납니다.