6042 : 스택 정렬 — 보조 스택 1개만
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
입력으로 임의의 정수 수열이 주어집니다. 이 수열을 입력 스택 1개와 보조 스택 1개만을 사용해 임시 리스트 없이 정렬하십시오.
최종적으로 스택의 top에서 원소를 꺼냈을 때 오름차순으로 정렬된 상태가 되어야 합니다.
[제약 조건]
• 원소 개수 $N$: $1 \le N \le 1{,}000$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
최종적으로 스택의 top에서 원소를 꺼냈을 때 오름차순으로 정렬된 상태가 되어야 합니다.
[제약 조건]
• 원소 개수 $N$: $1 \le N \le 1{,}000$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
입력 설명
첫째 줄에 원소의 개수 $N$이 주어집니다. ($1 \le N \le 1,000$)
둘째 줄에 스택에 저장할 $N$개의 정수가 공백으로 구분되어 주어집니다. (수열의 첫 번째 수가 스택의 top이 됩니다)
둘째 줄에 스택에 저장할 $N$개의 정수가 공백으로 구분되어 주어집니다. (수열의 첫 번째 수가 스택의 top이 됩니다)
출력 설명
정렬이 완료된 스택의 top부터 차례대로 꺼낸 원소들을 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
5 4 3 2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 4 5도움
6025번과 유사한 정렬 방식입니다. 입력 스택이 빌 때까지 임시 변수 `tmp`에 값을 두고, 보조 스택의 top이 `tmp`보다 작은 동안 보조 스택의 원소를 다시 입력 스택으로 되돌리는 과정을 반복합니다.