31719번 - UDP 스택 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 672 | 189 | 157 | 30.545% |
문제
UDP 마을에는 세 개의 신비한 스택이 있다. 이를 차례로 U스택, D스택, P스택이라 하자. 이 스택들은 특별해서 스택의 바닥을 열고 닫을 수 있다. 바닥이 열려 있는 스택에 원소를 삽입하면 그 즉시 바닥 아래로 떨어지며, 바닥이 닫혀 있는 스택의 바닥을 열면 저장되어 있던 원소들이 모두 바닥 아래로 떨어진다. 이때, 스택의 바닥에 가까운 쪽의 원소들이 더 먼저 바닥으로 떨어진다. 초기에는 U스택의 바닥만이 열려 있으며, D스택과 P스택의 바닥은 닫혀 있다.
어느 날, UDP 마을에서 길이가 $N$인 순열 $A$가 발견되었다. 포닉스는 다음 두 연산만을 사용할 수 있다.
- 순열 $A$의 가장 앞 원소를 세 스택 중 하나에 삽입한 후 순열에서 삭제한다. 단, 이 연산은 순열 $A$가 비어있지 않을 때만 가능하다.
- 현재 바닥이 열려 있는 스택을 닫은 후 바닥이 닫혀 있는 스택 중 하나를 골라 연다.
포닉스는 순열 $A$와 세 스택이 모두 빌 때까지 연산을 반복한 후, 먼저 떨어진 것이 앞에 오도록 원소들을 나열할 것이다. 포닉스가 원소들을 오름차순으로 재배열할 수 있을지 판별하여라.
입력
첫째 줄에 테스트케이스의 개수 $T$가 주어진다. $(1 \le T \le 500\ 000)$
각 테스트케이스의 첫째 줄에 순열의 길이 $N$이 주어진다. $(1 \le N \le 200\ 000)$
각 테스트케이스의 둘째 줄에 순열 $A$의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $A_i$는 $1$ 이상 $N$ 이하의 서로 다른 정수이다.
모든 테스트케이스에 대해 $N$의 합이 $500\ 000$ 이하임이 보장된다.
출력
각 테스트케이스에 대해 포닉스가 원소들을 오름차순으로 재배열하는 것이 가능하면 YES, 아니면 NO를 한 줄에 하나씩 순서대로 출력하여라.
예제 입력 1
3 5 1 4 5 3 2 4 1 4 3 2 5 4 5 3 2 1
예제 출력 1
YES YES NO
출처
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Junior Division E번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest E번
- 문제를 만든 사람: leo020630
- 문제를 검수한 사람: 99asdfg, hyperbolic, lky7674, mjhmjh1104, nick832, queued_q, slah007, tony9402, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호