[C++] 기차 운행

📄문제

A도시에서 출발한 기차는 B도시로 도착한다. 그런데 도로 중간에 T자형 교차로가 있어 출발한
기차의 도착 순서를 조정할 수 있다.

 

교차로에서는 다음과 같은 두 개의 작업을 합니다.
P(push)작업 : A도시에서 오는 기차를 교차로에 넣는다.
O(out)작업 : 교차로에 들어온 가장 최근 기차를 B도시로 보낸다.
만약 2 1 3 기차 번호 순으로 A도시에서 출발하더라도 B도시에는 T교차로를 이용하여 1 2 3 순으로 도착하게 할 수 있습니다.
그 작업 P, P, O, O, P, O순으로 작업을 하면 B도시에 1, 2, 3 순으로 도착합니다.
1부터 N까지 번호를 가진 기차가 A도시에서 어떤 순으로 출발하든, B도시에 번호순으로 도착하도록 하는 교차로 작업을 출력합니다. 모든 기차는 교차로에 들어가야만 B도시로 갈 수 있습니다. 

번호순서대로 도착이 불가능하면 impossible 이라고 출력합니다.

 

ℹ️ 조건

stack을 활용하여 문제를 해결합니다.

 

⬇️ 입력

첫 번째 줄에 자연수 N(3<=N<=30)가 주어진다.
두 번째 줄에 A도시에서 출발하는 기차번호순이 차례대로 입력된다.

3 2 1 3

 

⬆️ 출력

교차로 작업을 순서대로 P와 O로 출력한다.

PPOOPO

 

📝 풀이

#include <iostream>
#include <stack>
#include <queue>

using namespace std;
int main()
{
	int N;
	stack<int> stack;
	queue<char> queue;

	scanf_s("%d", &N);
	int* arr = new int[N];
	for (int i = 0; i < N; ++i)
		scanf_s("%d", &arr[i]);

	int nextTrainId = 1, idx = 0, deadLock = 0;
	while (1)
	{
		if (!stack.empty() && stack.top() == nextTrainId)
		{
			stack.pop();
			++nextTrainId;
			queue.push('O');

			if (stack.empty() && idx == N)
				break;
			else
				continue;
		}

		queue.push('P');
		stack.push(arr[idx++]);

		++deadLock;

		if (deadLock > N)
		{
			printf("impossible");
			return 0;
		}
	}

	while (!queue.empty())
	{
		printf("%c", queue.front());
		queue.pop();
	}
}

• stack을 활용하여 문제를 해결합니다.
• stack에 기차가 없거나, 다음 도착 기차번호가 아니라면 push 합니다.
• stack의 top에 다음 도착 번호의 기차라면, pop을 합니다.
• 만약에 deadlock이 N보다 크다면, 기차의 개수보다 많은 push를 요청한것이므로, impossible을 출력합니다.