55. 기차운행(stack 응용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>
#include <stack>
#include <vector>
using namespace std;

int a[31];
int b[31];
int main()
{
	int n, i = 1, j = 1;
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	for(int i = 1; i <= n; i++)
		b[i] = i;

	stack<int> s;
	vector<char> c;
	
	for(int i = 1; i <= n; i++)
	{
		s.push(a[i]);
		c.push_back('P');
		
		while(true)
		{
			if(s.empty())
				break;
				
			if(b[j] == s.top())
			{
				s.pop();
				c.push_back('O');
				j++;
			}
			else break;
		}
	}
	
	if(s.empty())
	{
		for(int k = 0; k < c.size(); k++)
			printf("%c", c[k]);
	}
	else
		printf("impossible");
	return 0;
}

1. 들어오는 기차의 번호를 저장할 배열 a, 1부터 n까지의 숫자를 저장할 배열 b, P작업, O작업을 할 때마다 그 작업을 저장할 vector c, 교차로에 들어온 기차의 순서를 저장할 stack s 를 선언한다.

2. 들어오는 기차를 먼저 stack에 push 후 P작업을 했기 때문에 c에 push_back('P') 를 해준다. 다음에 배열 b의 값과 비교해야하는데, 배열 b는 나가야할 기차의 번호를 지정해준다.

3. stack의 top(), 가장 맨 위 기차의 번호와 배열 b가 가리키는 번호가 같다면 그 기차를 pop() 하고 배열 b가 가리키는 포인터를 ++한다. 같지 않다면 다음 기차를 stack에 push한다.

4. 모든 작업이 끝났을 때 stack이 비어있지 않다면 기차가 제 차례 때 나가지 못한 것이므로 impossible을 출력한다.

 

바로 문제와 함께 설명해보겠다. 

기차가 2 1 3 순서로 출발했다. 그럼 먼저 2를 stack에 push한다.

c_push_back('P')

2

 

다음 배열 b가 가리키는 기차의 번호와 비교한다. 배열 b는 1부터 시작하기 때문에 최초에는 1과 비교한다.

2 != 1 이기 때문에 다음 기차를 push한다.

c_push_back('P')

2

1

 

다음 배열 b가 가리키는 기차의 번호와 비교한다.1 = 1 이므로 1번 기차가 나가야하는 순서이다. pop()을 해준다.

c_push_back('O')

2

다음 기차 번호를 가리키기 위해 j++을 해준다. 또 비교해본다. 2 = 2이다. pop()을 해준다.

다시 j++ 을 해준다.

c_push_back('P')

stack이 비었기 때문에 break 한다.

 

다음 3을 push한다. 이후 배열 b가 가리키는 번호와 비교한다. 3 = 3이기 때문에 pop()을 해준다.

c_push_back('O')

모든 작업이 끝났을 때 stack이 비었기 때문에 vector c의 원소를 모두 출력한다. (완료한 작업을 순서대로 출력)