기차운행(stack 응용) / c / 제한시간 없음

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

교차로 A도시 B도시 교차로에서는 다음과 같은 두 개의 작업을 합니다.

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로 출력한다.

 

▣ 입력 예시

3 2 1 3

 

▣ 출력 예시

PPOOPO

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int stack[30];
int top = -1;

void push(int x) {
	stack[++top] = x;
}

int pop() {
	return stack[top--];
}

int main() {
	int n, i;
	int k = 1;
	int num = 1;
	int train[31];
	char ans[100];
	int p = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &train[i]);
	}

	while (num <= n) {
		if (stack[top] == num) {
			pop();
			ans[p++] = 'O';
			num++;
			continue;
		}
		else if (train[k] != NULL) {
			push(train[k++]);
			ans[p++] = 'P';
		}
		else {
			printf("impossible\n");
			return 0;
		}
	}
	ans[p++] = '\0';
	printf("%s", ans);
	return 0;
}

ans[ ] 는 'P' 와 'O'를 저장하기 위한 배열이고 train[ ] 는 입력받는 기차번호순 을 저장하기 위한 배열이다.

 

기차를 순서대로 저장한 후에 while 문을 통해서 stack에 PUSH 또는 POP을 실행한다.

 

while 문에서는 num는 B도시에 도착해야하는 열차의 순서를 의미한다.

 

train[ ] 배열을 처음부터 하나씩 읽어서 만약 stack[top] 과 같다면 POP을 실행하고 'O'를 저장한다.

 

그렇지 않다면 PUSH를 실행하고 'P'를 저장한다.

 

만약 train[ ]을 끝까지 읽었는데 num와 stack[top]이 다르다면 번호순서대로 도착이 불가능하기 때문에 'impossible'을 출력하고 프로그램을 종료한다.

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int stack[30];
int top = -1;

void push(int x) {
	stack[++top] = x;
}

int pop() {
	return stack[top--];
}

int isEmpty() {
	if (top != -1) return 0;
	else return 1;
}

int main() {
	int n, i, temp;
	int p = 0;
	int j = 1;
	int num = 1;
	char ans[100];

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &temp);
		push(temp);
		ans[p++] = 'P';
		while (1) {
			if (isEmpty()) break;
			if (j == stack[top]) {
				pop();
				j++;
				ans[p++] = 'O';
			}
			else break;
		}
	}
	if (!isEmpty()) printf("impossible\n");
	else {
		ans[p++] = '\0';
		printf("%s", ans);
	}
	return 0;
}

 temp를 통해서 A도시에서 오는 기차의 번호를 받는다.

 

기차가 들어오면 일단 교차로에 들어가기 때문에 PUSH를 해주고 ans[ ]에 'P'를 저장한다.

 

그리고 while문을 통해서 stack[top]과 비교를 시작한다. j는 차례대로 B도시에 도착해야하는 기차의 순서를 의미한다.

 

만약 j 와 stack[top]이 같으면 POP을 해주고 ans[ ] 에 'O'를 저장한다.

 

그리고 계속 비교해가는 과정에서 stack이 비어있으면 break 문을 걸어둔다.

 

for 문이 끝나고 만약 스택이 비어있지 않으면 기차번호가 순서대로 도착이 불가능하다는 뜻이기 때문에 'impossible'을 출력해준다.

 

그렇지 않으면 저장한 ans[ ]을 출력해준다.

 

.

 

문자열의 크기를 대략 잡고 시작했기 때문에 ans[p++]='\0 을 통해서 문자열의 끝을 저장해야 나중에 출력을 할 수 있다.