6043 : 수열 스택 — 출력 순서 판별
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
1부터 $N$까지의 수를 스택에 차례대로 넣었다가 빼는(push, pop) 동작을 반복하여, 주어진 목표 수열을 만들어낼 수 있는지 판별하는 프로그램을 여러 테스트 케이스에 대해 작성하십시오.
스택에 카드를 넣는 연산은 항상 오름차순(1, 2, ..., N 순서)으로만 진행됩니다.
[제약 조건]
• 테스트케이스 수 $T$: $1 \le T \le 100$ (정수)
• 각 수열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 수열은 1부터 $N$까지의 순열입니다.
스택에 카드를 넣는 연산은 항상 오름차순(1, 2, ..., N 순서)으로만 진행됩니다.
[제약 조건]
• 테스트케이스 수 $T$: $1 \le T \le 100$ (정수)
• 각 수열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 수열은 1부터 $N$까지의 순열입니다.
입력 설명
첫째 줄에 테스트케이스의 개수 $T$가 주어집니다. ($1 \le T \le 100$)
각 테스트케이스는 다음과 같이 두 줄로 구성됩니다.
- 첫 번째 줄에 수열의 크기 $N$이 주어집니다. ($1 \le N \le 100,000$)
- 두 번째 줄에 $1$부터 $N$까지의 수로 이루어진 순열이 공백으로 구분되어 주어집니다.
각 테스트케이스는 다음과 같이 두 줄로 구성됩니다.
- 첫 번째 줄에 수열의 크기 $N$이 주어집니다. ($1 \le N \le 100,000$)
- 두 번째 줄에 $1$부터 $N$까지의 수로 이루어진 순열이 공백으로 구분되어 주어집니다.
출력 설명
각 테스트케이스에 대해 수열을 만들어낼 수 있다면
YES, 불가능하다면 NO를 줄바꿈하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
8
4 3 6 8 7 5 2 1
5
1 2 5 3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES
NO도움
6030번(스택 수열 만들기)과 동일한 논리를 사용하되, 여러 테스트 케이스에 대해 각각 큐/스택 메모리를 초기화하여 순회합니다.