BOJ - 18258 큐 2 해결 전략 (C++)

• 문제 링크
  백준 18258번 - 큐 2

해결 전략

  본 문제는 며칠 전 포스팅했던 BOJ - 10828 스택 해결 전략 (C++) 게시글과 같은 유형의 문제이다.

  그 때와 마찬가지로, 물론 vector stl이나 list stl을 이용해서 간단히 해결할 수 있겠지만, 그러한 자료구조 라이브러리 없이 Naive하게 큐를 구현하는 것이 본 목적이므로 직접 일일이 큐를 구현하였다.

  본 문제는 앞선 스택 문제와 다르게 한 가지 유의할 점이 있는데, 문제의 입력 제한이 2,000,000이기 때문에 Pop을 구현하는 과정에서 단순한 Linear Traverse를 이용하면 시간 초과가 난다는 것이다. (참고로, 자료구조 구현 스킬은 이미 알고 있는 사람을 대상으로 포스팅한다. 이에 대한 조언은 위의 '스택' 포스팅에 적어두었다.)

시간 초과를 피하기 위해선 결국 Doubly Linked List가 필요하다.

  즉, 일방향의 link로 구조체를 만들고 큐를 구현 시 필연적인 선형 순회가 필요하고, 이 문제의 조건 상에서 이는 시간 초과의 대상이라는 점이다. 따라서 양방향 link가 필요하다. 다만, 문제 조건 상, Pop을 할 때 외에는 front link가 필요치 않으므로 엄밀하게 link관계를 구성할 필요는 없다는 점이다.

  Push 상황에서 size가 1 이상일 때부터 Push 시 front link를 연결해주고, Pop 상황에서는 단순하게 tail이 tail의 front link를 따라가게만 구성해주면 된다는 것이다.

  아무튼, 결론적으로 본 문제를 통해 얻을 수 있는 교훈은 다음과 같다.

큐를 만들 때는, 양방향의 연결 관계가 있어야 효율적이다. 귀찮더라도 본 문제같은 문제를 맞이한다면, 더블리로 연결관계를 구축하도록 하자.

  아래는 코드이다.

#include <iostream>
#include <string>
// BOJ - 18258 Queue 2
using namespace std;

typedef struct _node {
	int key;
	struct _node *link;
	struct _node *f_link;
}Node;

Node *head = NULL, *tail = NULL;
int queueCnt = 0;

bool qEmpty(void) { if (queueCnt == 0) return true; return false; }

void qPush(int x) {
	Node *newNode = new Node;
	newNode->key = x;

	newNode->link = head;
	newNode->f_link = NULL;
	if (queueCnt > 0)
		head->f_link = newNode;
	head = newNode;
	if (queueCnt == 0) tail = newNode;

	queueCnt++;
}


void qPop(void) {
	if (qEmpty()) { cout << -1 << '\n'; return; }
	Node *delNode = tail;

	if (queueCnt == 1) 
		head = tail = NULL;
	else {
		tail = tail->f_link;
		tail->link = NULL;
	}
	cout << delNode->key << '\n';
	delete[] delNode;

	queueCnt--;
}

void qSize(void) { cout << queueCnt << '\n'; }

void qFront(void) { if (qEmpty()) cout << -1 << '\n'; else cout << tail->key << '\n'; }

void qBack(void) { if (qEmpty()) cout << -1 << '\n'; else cout << head->key << '\n'; }

int main(void) {
	int n, num; string option;
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	while (n--) {
		cin >> option;
		switch (option[0]) {
		case 'p': 
			if (option[1] == 'u') {
				cin >> num;
				qPush(num);
			}
			else qPop(); break;
		case 's': qSize(); break;
		case 'f': qFront(); break;
		case 'b': qBack(); break;
		case 'e': cout << qEmpty() << '\n'; break;
		}
	}

	return 0;
}