55. 기차운행 (스택 자료구조 응용) [정렬 & 이분탐색(결정알고리즘) & 투포인트 알고리즘 & 스택]

나의정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, i = 1, j = 0, start, count = 0;
	
	scanf("%d", &n);
	stack<int> s;
	char* a = new char[n * 2];

	while (count < n) {
		scanf("%d", &start);
		s.push(start);
		a[j++] = 'P';

		while (!s.empty() && s.top() == i) {
			s.pop();
			a[j++] = 'O';
			i++;
		}

		count++;
	}

	if (s.empty()) {
		for (i = 0; i < j; i++)
			printf("%c", a[i]);
	}
	else
		printf("impossible\n");

	delete[] a;
}