6030 : 스택으로 수열 만들기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
1부터 $N$까지의 수를 스택에 차례대로 넣었다가(push) 빼는(pop) 동작을 반복하여, 주어진 임의의 목표 수열을 만들어낼 수 있는지 판별하십시오.
스택에 넣는 연산은 항상 오름차순(1, 2, ..., N 순서)으로만 가능합니다.
스택에 넣는 연산은 항상 오름차순(1, 2, ..., N 순서)으로만 가능합니다.
입력 설명
첫째 줄에 수열의 크기 $N$이 주어집니다. ($1 \le N \le 100,000$)
둘째 줄에 1부터 $N$까지의 수로 이루어진 순열(목표 수열)이 공백으로 구분되어 주어집니다.
둘째 줄에 1부터 $N$까지의 수로 이루어진 순열(목표 수열)이 공백으로 구분되어 주어집니다.
출력 설명
수열을 만들 수 있다면 연산 순서에 맞게
만약 수열을 만들어내는 것이 불가능하다면 단 한 줄에
push 또는 pop을 줄바꿈으로 출력합니다.만약 수열을 만들어내는 것이 불가능하다면 단 한 줄에
NO를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
4 3 6 8 7 5 2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
push
push
push
push
pop
pop
push
push
pop
push
push
pop
pop
pop
pop
pop도움
1부터 $N$까지의 값을 증가시키면서 스택에 push합니다. 스택의 top이 목표 수열의 현재 가리키는 값과 같다면 계속 pop을 시도합니다.