★ solved.ac 난이도 : S3
(2021년 12월 29일 기준)
[문제 링크]
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
[문제 분석]
스택의 push 연산과 pop 연산을 응용한 깊이 있는(?) 문제
[풀이]
이 문제는, 스택의 push 연산과 pop 연산을 활용한 심화 문제라고 볼 수 있습니다.
1부터 n까지의 수들이 오름차 순으로 push가 된다고 합니다.
push 연산을 이어가면서, 수열의 데이터와 비교하고, 맨 꼭대기의 값과 일치한다면, 스택에서 데이터를 꺼내고 출력하게 됩니다.
(단, 한 번에 여러 개의 수가 pop이 되는 경우도 있습니다.)
이 과정을 끝까지 반복하고 나서, 스택이 비어있지 않다면, 불가능한 경우입니다.
(주의!!)
여기에서 과정을 출력하면서 마지막에 'NO'를 출력하게 된다면, 출력 초과를 받을 수 있습니다.
따라서, 과정을 임시로 저장해두고, 마지막에 스택이 비어있음을 확인 후, 결과를 출력하셔야합니다.
그리고, 불가능한 경우에는 'NO'만 출력하셔야 합니다.
[소스 코드]
만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)