1874 스택

스택에 입력이 1부터 N까지 차례대로 들어온다고 할 때,
출력된 결과를 가지고 Push 와 Pop 여부를 가리는 문제이다.

이 문제를 풀기 위해선 일단 스택처럼 사용할 배열이 필요하다.
배열을 잡아주었으면 입력을 하나씩 받아와 처리하면 되는데,
push와 pop 여부를 알기위해선 입력된 값들의 최대값을 저장하는 max변수가 필요하다.
max변수의 시작은 0이다.

나머지 과정을 예를들어 설명하자면, max 변수의 값이 0인 상태에서 입력으로 4가 들어왔다고 하자.
그러면 우선 4까지 push 됬다는 의미 이므로 Push Push Push Push 가 되고,
4가 출력됬으므로 Pop이 된다.
그러면 스택에 저장되있는값은 1,2,3 이고, max값은 4가 된다.

이 상태에서 다음 입력이 3이라고 하자. 그러면 max보다 작기때문에 push를 한것이 아니고 Pop만 해준것이다. 그러므로 Pop 한번이고 스택의 값은 1,2 가 된다. max값은 변함없다.

이 때, 입력으로 3이아니라 2가들어오면 이것은 잘못된 입력이다. 왜냐하면 2로 가기위해선 2번이 Pop되야하는데 이 과정에서 3이 출력되기 때문이다.

3다음에 6이 들어왔다고 하자. 그러면 max값이 4고, 5 6이 Push된 것이므로
Push Push 가 되고, 6이 출력됬으므로 Pop이 한번 실행된다.
이 때 스택안의 값은 1,2,5가 된다.

이런식으로 스택을 구현해주고 검사를하면 답을 얻을 수 있다.

소스