boj 1874 : 스택 수열

boj 1874 : 스택 수열

https://www.acmicpc.net/problem/1874

스택수열은 큐와 스택으로 해결된다.

1. Ai : i번째 문자

2. queue : 1~N까지 순서대로 담켜있다.

3. stack : stack의 top은 0.

- 여기까지가 전처리.

1. Ai가 queue의 front보다 같거나 작을 때까지 queue를 pop하고 stack에 push.;

2. Ai가 stack의 top과 같으면 pop.

3. i++

1,2,3의 과정을 반복하면 답을 구할 수 있다.

올바르지 않은 수열은 어떻게 구할 수 있을까?

stack의 top보다 Ai가 작다면 만들어질 수 없는 스택수열이다.

stack의 top보다 Ai가 작으면 stack의 pop 과정이 이루어진 후에 Ai를 pop할 수 있는데, 이것은 이미 주어진 스택수열과 다르기 때문.