[백준 BOJ] 12789 도키도키 간식드리미 C++

백준 12789번: 도키도키 간식드리미

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

12789번: 도키도키 간식드리미

---

문제

예제

• 문제해석 및 풀이

 이 문제는 문제가 길어서 어렵게 느껴질 수 있지만 문제의 핵심 부분만 놓고 보면 그렇게 어렵지 않은 문제이다. 줄을 서고 있는 학생의 수가 주어지고 이어서 그 학생들의 번호표 숫자가 서 있는 순서대로(=> 큐와 같은 구조) 주어진다. 옆으로 빠질 수 있는 공간은 사람이 한 명밖에 지나가지 못하고(=> 스택과 같은 구조) 따라서 현재 줄을 서 있는 순서에 따라서 승환이가 간식을 받을 수 있을 수도 있고 없을 수도 있다.

 승환이가 간식을 받기 위해서는 스택이 비어있어야 한다. 승환이 앞에 있는 모든 사람들이 간식을 받아야 한다는 의미이다. 큐의 맨 앞 숫자가 간식을 받을 차례의 번호이면 그 번호를 삭제하고 번호표 숫자를 1올린다. 마찬가지로 스택의 맨 위의 숫자가 간식을 받을 차례의 번호이면 그 번호를 삭제하고 번호표 숫자를 1올린다. 두 가지 경우에 모두 해당이 되지 않는 경우에는 큐의 맨 앞 숫자를 스택으로 넣는다. 이런 방식으로 진행하다가 스택이 비어있으면 간식을 받은 것이고 반대의 경우이면 간식을 받지 못한 것이다.

 

• 코드

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, input;
	int cnt = 1;
	queue<int> now;
	stack<int> wait;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		now.push(input);
	}
	while (1) {
		if (!now.empty() && now.front() == cnt) {
			now.pop();
			cnt++;
		}
		else if (!wait.empty() && wait.top() == cnt) {
			wait.pop();
			cnt++;
		}
		else {
			if (now.empty())
				break;
			wait.push(now.front());
			now.pop();
		}
	}
	if (wait.empty())
		cout << "Nice";
	else
		cout << "Sad";
	return 0;
}

 stack과 마찬가지로 queue도 C++에서 제공하는 STL이다. queue는 후입선출인 stack과 다르게 선입선출인 자료구조이다. 여기서 쓰인 front함수는 큐의 첫번째 데이터를 반환하는 함수이다.

 이 코드에서는 무한루프의 내용이 핵심이다. 무한루프 내의 첫번째 및 두번째 조건문은 큐와 스택의 앞 데이터가 현재 번호표 숫자와 같으면 그 데이터를 삭제하고 번호표 숫자를 1 올리는 내용이다. 마지막 조건문은 위의 상황에 해당하지 않는 상황에 큐에 줄이 없으면 무한루프를 종료하고 큐에 줄이 남아 있으면 큐의 맨 앞 데이터를 스택으로 보내는 내용이다.

 

• 정리

 이 문제를 처음에는 배열과 스택을 이용해 풀어서 코드가 복잡해지고 제출 결과도 틀렸다. 고민을 많이 하다가 큐를 이용해 보기로 했다. 큐를 이용하니 코드도 간결해지고 결과도 맞았다. 문제 자체는 어려워 보이지 않는 구조를 띄고 있지만 문제를 해결하는 것은 상당히 까다로웠던 문제였다.

 

 궁금한 것이나 더 나은 코드 및 방법, 그리고 잘못된 것이 있다면 댓글에 남겨주시기 바란다.