[알골90제] 55번 - 기차운행 : STACK 응용

*문제 

 

입력

3

2 1 3

 

출력

PPOOPO

 

결과

A도시에 입력된 결과가 오름차순 (ex.1 2 3) 순으로 B도시에 도착하게 함

 

 

*생각

 

- 스택을 써야하 함

- 조건문 어떻게 달아야 하나, 스택에 넣고, 순서대로 빼는 조건문?

 

 

*문제 풀이

- 주의! 모든 기차는 교차로에 들어갔다가 B도시에 가야한다.

 

0) B도시에 순서대로 1 2 3 4 배열을 만들어서 놓는다.

1) 3을 스택에 push한다.

2) push를 했으면 이걸 char 배열에도 P를 넣어야함 나중에 P를 출력해야하니깐

3) stack의 제일 위에 있는 ex.3과 j가 가리키는 부분이 같은지 봐야함. 같지 않으면 넘어감

4) 그 다음 1을 읽어서 스택에 push.. char P

5) 1과 j가 가리키는 곳이 1로 모두 같음. =>pop 하고 j는 ++ => char 배열에 O

.

.

.

.

stack이 empty이면 break;

그러고 다시 4 읽고 stack에 push P, 

Stack이 empty면 그만두기.

 

 

*Impossible인 경우

다 읽고 스택에 넣었는데 1,2,3,4 순으로 도착안되면 impossible

 

 

 

// 55번 - 기차운행(Stack 응용)

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

int main() {

	stack<int> s;
	int n, t, j=1;

	scanf("%d", &n);

	vector<char> str;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &t);
		s.push(t);
		str.push_back('P');

		while (1) {
			if (s.empty()) //스택이 비어있으면
				break;
			if (j == s.top()) {
				s.pop();
				str.push_back('O');
				j++;
			}
			else break;
		}
	}

	if (!s.empty()) printf("impossible\n");
	else {
		for (int i = 0; i < str.size(); i++) //10개 넣었으면 size가 10개 (공간 10개)
			printf("%c", str[i]);
	}
	return 0;

}