🙇‍♀️기차운행(stack 응용)

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 이라고 출력합니다.

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=30)가 주어진다.

두 번째 줄에 A도시에서 출발하는 기차번호순이 차례대로 입력된다.

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

▣ 입력예제 1 
3
2 1 3

▣ 출력예제 1
PPOOPO

🚀풀이

나는 값을 입력 받을 때 스택의 상황을 비교하면서 문제를 풀었다.

코드는 다음과 같다.

int n, pos = 1;
stack<int> s;
string str;

void solve()
{
	cin >> n;

	int temp;
	for (int i = 1; i <= n; ++i)
	{
		cin >> temp;
		if (temp > pos)
		{
			if (s.empty() == false && s.top() == pos)
			{
				while (true)
				{
					if (s.empty())
						break;
					if (s.top() != pos)
						break;

					s.pop();
					str += "O";
					pos++;
				}
			}

			{
				s.push(temp);
				str += "P";
			}
		}
		else if (temp < pos)
		{
			cout << "impossible";
			return;
		}
		else if (temp == pos)
		{
			str += "P";
			str += "O";
			pos++;
		}
	}

	if (s.empty() == false)
	{
		while (true)
		{
			if (s.empty())
				break;
			if (s.top() != pos)
			{
				cout << "impossible";
				return;
			}

			s.pop();
			str += "O";
			pos++;
		}
	}

	cout << str;
}

pos라는 변수로 지금 몇 번째 기차가 필요한지 체크를 한다.

각 경우에대하여 경우의 수를 다 생각해서 문제를 풀었다.

🚀강의를 듣고 수정한 코드

강의에서는 일단 값이 들어오면 스택에 push를 하고 그 다음 비교를 했다.

확실히 이 방법이 더 좋은거같아서 코드를 수정했다.

int n, pos = 1;
stack<int> s;
string str;

void solve()
{
	cin >> n;

	int temp;
	for (int i = 1; i <= n; ++i)
	{
        // 값이 들어오면 일단 push
		cin >> temp;
		s.push(temp);
		str += 'P';

        // 스택의 상황과 비교를 시작한다.
		while (true)
		{
			if (s.empty())
				break;
			if (s.top() != pos)
				break;
            
            // 여기까지 오면 스택의 맨 위가 원하는 기차의 숫자이다.
			s.pop();
			pos++;
			str += 'O';
		}
	}

    // 스택이 남아 있다는 것은 조합이 불가능한 경우이다.
    // 가능한 경우가 나오면 무조건 pop을 다 해주었기 때문.
	if (s.empty() == false)
	{
		cout << "impossible";
		return;
	}

	cout << str;
}

이전에 이와 비슷한 문제를 풀었는데 깔끔하게 못풀어서 아쉬웠다.

그래도 정답은 맞았으니 다행..

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int n, pos = 1;
stack<int> s;
string str;

void solve()
{
	cin >> n;

	int temp;
	for (int i = 1; i <= n; ++i)
	{
		cin >> temp;
		s.push(temp);
		str += 'P';

		while (true)
		{
			if (s.empty())
				break;
			if (s.top() != pos)
				break;

			s.pop();
			pos++;
			str += 'O';
		}
	}

	if (s.empty() == false)
	{
		cout << "impossible";
		return;
	}

	cout << str;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고