사용 가능 함수
- write, read, malloc, free, exit
규칙
스택 a에는 중복되지 않는 랜덤 개수의 숫자
스택 b는 빈 스택
목표
스택 a를 오름차순으로 정렬
연산
1. swap
sa: a의 맨 위 2개 요소를 스왑
(요소가 없거나 1개면 아무것도 하지 않음)sb: b의 맨 위 2개 요소를 스왑
(요소가 없거나 1개면 아무것도 하지 않음)ss:sa와sb동시에 실행
2. push
pa: b의 맨 위 요소를 a의 맨 위에 푸시
(b가 비어 있으면 아무것도 하지 않음)pb: b의 맨 위 요소를 a의 맨 위에 푸시
(b가 비어 있으면 아무것도 하지 않음)
3. rotate
ra: a의 모든 요소를 한 칸씩 위로 밀어올림
(맨 위의 요소를 맨 아래로 보내기)rb: b의 모든 요소를 한 칸씩 위로 밀어올림
(맨 위의 요소를 맨 아래로 보내기)rr:ra와rb를 동시에 실행
4. reverse rotate
rra: a의 모든 요소를 한 칸씩 아래로 밀어내림
(맨 아래 요소를 맨 위로 보내기)rrb: b의 모든 요소를 한 칸씩 아래로 밀어내림
(맨 아래 요소를 맨 위로 보내기)rrr:rra와rrb를 동시에 실행
입출력
- push_swap 프로그램의 인자는 스택 a에 들어갈 정수 목록
(첫 번째 인자가 맨 위 요소) - 스택을 정렬하는 가장 적은 수의 명령을
\n으로 구분하여 콘솔에 출력 - 에러가 발생하면
Error\n를 stderr에 표시
(에러는 인자가 정수가 아니거나, 정수 범위를 넘어서거나, 중복 인자가 있는 경우 등 포함)
구현
- rotate 연산을 쉽게 처리하기 위해 이중 원형 연결 리스트 사용
(헤드 노드가 맨 위 요소를 가리킴)
- 인자 파싱, 유효성 검사
- a가 이미 정렬되었는지 확인 (그렇다면 프로그램 종료)
- a의 크기가 5 이하면 예외 처리 함수 실행, 아니면 일반 정렬 함수 실행
파싱
- 공백 처리
예)"123 3 0" 2 5 - 유효성 검사
- 모두 숫자인지
- 정수 범위에 포함되는지
- 중복되지 않는지
스택 연산
- 첫 번째 인자가 top이 되어야 하므로 순서대로 끝에 삽입해야 함
정렬
- 일단 스택이 정렬된 상태인지 (프로그램을 수행할 필요가 없는지) 먼저 검사!
- 2개의 피봇을 가지고 3등분
큰 피봇보다 작은 값은 b로 넘기고 b 안에서 작은 피봇 기준으로 나누기
정렬 준비
- 버블 정렬로 미리 정렬해서 인덱스 부여
- 3등분해서 큰 피봇과 작은 피봇 구하기
1차 정렬
- a에서 큰 피봇보다 작은 값은
pb, 아니면ra - 1에서
pb후 b 안에서 작은 피봇보다 큰 값은rb rb한 만큼rrb해서 작은 피봇보다 큰 값을 위로 올리기 (100개 이하에서는 이 과정 생략)
👉 반복적으로 3등분된 값들이 b에 들어가서 대충 내림차순으로 쌓임
2차 정렬
(100개 이하인 경우 바로 b에서 가장 큰 값을 찾아서 rb 또는 rrb 후 pa로 모두 옮기고 끝냄)
1. 1차 정렬의 각 3등분 과정에서 작은 피봇보다 큰 수들에 대해 3등분 정렬 (rb rrb pa)
2. b에는 2차 정렬 후 가장 작은 값만 남으므로 그만큼의 수를 pa
(이때 한 덩어리의 크기가 100보다 크면 2번 없이 3개 이하로 남을 때까지 반복 3등분)
3. 남은 3개 이하의 값을 pa로 다 꺼냄
👉 반복 후 모든 값은 a에 대충 오름차순으로 쌓임
3차 정렬
- a에서 가장 작은 값을 찾아서
ra또는rra한 뒤pb
👉 완벽한 내림차순 정렬 - 모두
pa
평가 기준
3: 3회5: 12회100: 700 / 900 / 1100 / 1300 / 1500500: 5500 / 7000 / 8500 / 10000 / 11500
100개, 500개 테스트 점수를 더해서 6점 이상이어야 통과
터미널 난수 생성
ruby -e "puts (1..500).to_a.shuffle.join(' ')"
참고
https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50
push_swap 비주얼라이저
테스터
