-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
55. 기차 운행
21.01.10 19:01 작성 조회수 157
0
안녕하세요 55. 기차 운행(스택) 문제를 좀 다르게 풀었는데 마지막 예시가 자꾸 틀려요. 도와주세요ㅜ
stack[top]보다 큰 수가 push 되면 스택 구조니까 순서가 맞을 수 없다고 생각하면서 풀었어요
배열 a: input
배열 result : 출력할 결과
배열 b : 스택에서 꺼낸 숫자 저장
i=1 ; i<n ; i++
{a[i]와 stack[top]을 비교해서 - 1)a[i] > stack[top]
스택이 비워질 때까지 or a[i]<stack[top] 일 때까지 pop
{ pop한 숫자를 배열 b에저장
(방금 저장한) pop한 숫자와 배열 b에 이전에 넣은 수를 빼서 차가 1이 아니면 impossible + 종료
result[++]='O' }
push(a[i]) , result[++]='P'
i++
-2) a[i] < stack[top]
push(a[i]) , result[++]='P'
i++
}
스택이 empty 될 때까지
{ pop한 숫자를 배열 b에저장
(방금 저장한) pop한 숫자와 배열 b에 이전에 넣은 수를 빼서 차가 1이 아니면 impossible + 종료
result[++]='O' }
결과 출력
이렇게 했어요
코드는 c로 풀었습니다
#pragma warning (disable :4996)
#define M 60
#include<stdio.h>
int top = -1;
int stack[M] = { 0 };
int b[30] = { 0 };
void push(int n)
{
stack[++top] = n;
}
int pop()
{
return stack[top--];
}
int main(void)
{
int n=0;
int a[30] = { 0 };
char result[M] = { 'P' };
int r = 0, B = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
push(a[0]);
for (int i = 1; i < n; i++)
{
if (a[i] > stack[top])
{
while (top > -1&&a[i]>stack[top])
{
b[B]=pop();
result[++r] = 'O';
if (B > 0 && (b[B] - b[B - 1] != 1))
{
printf("impossible");
return 0;
}
++B;
}
push(a[i]);
result[++r] = 'P';
}
else
{
push(a[i]);
result[++r] = 'P';
}
}
while (top > -1)
{
b[B] = pop();
result[++r] = 'O';
if (b[B] - b[B - 1] != 1)
{
printf("impossible");
return 0;
}
B++;
}
for (int j = 0; j <=r; j++)
printf("%c", result[j]);
return 0;
}
답변을 작성해보세요.
0
답변 1