6081 : 두 스택으로 정렬된 삽입
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
두 스택으로 정렬된 삽입
두 개의 스택만을 사용하여 새로운 원소가 들어올 때마다 항상 오름차순 정렬 상태를 유지하시오.
알고리즘:
1. 삽입 스택(main)에서, 새 원소 x보다 큰 값들을 임시 스택(tmp)으로 옮깁니다.
2. main에 x를 삽입합니다.
3. tmp의 원소들을 다시 main으로 옮깁니다.
최종적으로 main 스택 아래(인덱스 0)부터 위까지 오름차순으로 출력합니다.
[제약 조건]
• 원소 개수 $N$: $1 \le N \le 1{,}000$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
두 개의 스택만을 사용하여 새로운 원소가 들어올 때마다 항상 오름차순 정렬 상태를 유지하시오.
알고리즘:
1. 삽입 스택(main)에서, 새 원소 x보다 큰 값들을 임시 스택(tmp)으로 옮깁니다.
2. main에 x를 삽입합니다.
3. tmp의 원소들을 다시 main으로 옮깁니다.
최종적으로 main 스택 아래(인덱스 0)부터 위까지 오름차순으로 출력합니다.
[제약 조건]
• 원소 개수 $N$: $1 \le N \le 1{,}000$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
입력 설명
첫째 줄에 삽입할 원소의 개수 N (1 ≤ N ≤ 5,000)이 주어집니다.
둘째 줄에 N개의 정수가 삽입 순서대로 공백으로 구분되어 주어집니다.
둘째 줄에 N개의 정수가 삽입 순서대로 공백으로 구분되어 주어집니다.
출력 설명
모든 원소를 삽입한 후 스택 내부를 아래부터 위 순서(오름차순)로 공백 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
3 1 4 1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 1 3 4 5