push_swap

chez_bono·2021년 12월 28일
0

42cursus

목록 보기
5/17
post-thumbnail

사용 가능 함수

  • write, read, malloc, free, exit

규칙

스택 a에는 중복되지 않는 랜덤 개수의 숫자
스택 b는 빈 스택

목표

스택 a를 오름차순으로 정렬

연산

1. swap

  • sa: a의 맨 위 2개 요소를 스왑
    (요소가 없거나 1개면 아무것도 하지 않음)
  • sb: b의 맨 위 2개 요소를 스왑
    (요소가 없거나 1개면 아무것도 하지 않음)
  • ss: sasb 동시에 실행

2. push

  • pa: b의 맨 위 요소를 a의 맨 위에 푸시
    (b가 비어 있으면 아무것도 하지 않음)
  • pb: b의 맨 위 요소를 a의 맨 위에 푸시
    (b가 비어 있으면 아무것도 하지 않음)

3. rotate

  • ra: a의 모든 요소를 한 칸씩 위로 밀어올림
    (맨 위의 요소를 맨 아래로 보내기)
  • rb: b의 모든 요소를 한 칸씩 위로 밀어올림
    (맨 위의 요소를 맨 아래로 보내기)
  • rr: rarb를 동시에 실행

4. reverse rotate

  • rra: a의 모든 요소를 한 칸씩 아래로 밀어내림
    (맨 아래 요소를 맨 위로 보내기)
  • rrb: b의 모든 요소를 한 칸씩 아래로 밀어내림
    (맨 아래 요소를 맨 위로 보내기)
  • rrr: rrarrb를 동시에 실행

입출력

  • push_swap 프로그램의 인자는 스택 a에 들어갈 정수 목록
    (첫 번째 인자가 맨 위 요소)
  • 스택을 정렬하는 가장 적은 수의 명령을 \n으로 구분하여 콘솔에 출력
  • 에러가 발생하면 Error\n를 stderr에 표시
    (에러는 인자가 정수가 아니거나, 정수 범위를 넘어서거나, 중복 인자가 있는 경우 등 포함)

구현

  • rotate 연산을 쉽게 처리하기 위해 이중 원형 연결 리스트 사용
    (헤드 노드가 맨 위 요소를 가리킴)
  1. 인자 파싱, 유효성 검사
  2. a가 이미 정렬되었는지 확인 (그렇다면 프로그램 종료)
  3. a의 크기가 5 이하면 예외 처리 함수 실행, 아니면 일반 정렬 함수 실행

파싱

  • 공백 처리
    예) "123 3 0" 2 5
  • 유효성 검사
    • 모두 숫자인지
    • 정수 범위에 포함되는지
    • 중복되지 않는지

스택 연산

  • 첫 번째 인자가 top이 되어야 하므로 순서대로 끝에 삽입해야 함

정렬

  • 일단 스택이 정렬된 상태인지 (프로그램을 수행할 필요가 없는지) 먼저 검사!
  • 2개의 피봇을 가지고 3등분
    큰 피봇보다 작은 값은 b로 넘기고 b 안에서 작은 피봇 기준으로 나누기

정렬 준비

  1. 버블 정렬로 미리 정렬해서 인덱스 부여
  2. 3등분해서 큰 피봇과 작은 피봇 구하기

1차 정렬

  1. a에서 큰 피봇보다 작은 값은 pb, 아니면 ra
  2. 1에서 pb 후 b 안에서 작은 피봇보다 큰 값은 rb
  3. rb한 만큼 rrb해서 작은 피봇보다 큰 값을 위로 올리기 (100개 이하에서는 이 과정 생략)
    👉 반복적으로 3등분된 값들이 b에 들어가서 대충 내림차순으로 쌓임

2차 정렬

(100개 이하인 경우 바로 b에서 가장 큰 값을 찾아서 rb 또는 rrbpa로 모두 옮기고 끝냄)
1. 1차 정렬의 각 3등분 과정에서 작은 피봇보다 큰 수들에 대해 3등분 정렬 (rb rrb pa)
2. b에는 2차 정렬 후 가장 작은 값만 남으므로 그만큼의 수를 pa
(이때 한 덩어리의 크기가 100보다 크면 2번 없이 3개 이하로 남을 때까지 반복 3등분)
3. 남은 3개 이하의 값을 pa로 다 꺼냄
👉 반복 후 모든 값은 a에 대충 오름차순으로 쌓임

3차 정렬

  1. a에서 가장 작은 값을 찾아서 ra 또는 rra한 뒤 pb
    👉 완벽한 내림차순 정렬
  2. 모두 pa

평가 기준

  • 3: 3회
  • 5: 12회
  • 100: 700 / 900 / 1100 / 1300 / 1500
  • 500: 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 비주얼라이저
테스터

profile
목표는 행복한 베짱이

0개의 댓글