42서울 본과정 - Push_Swap

📒 Technical consideration

when

• 23.07.14 15:00 ~

내용

제출 파일	Makefile, .h, .c
Makefile	NAME, all, clean, fclean, re
외부 함수	read, write, malloc, free, exit, ft_printf
매개변수	읽어들일 파일의 descriptor (서술자)
인자	stack a: A list of integers
libft 사용	허용

📌 주의사항

• norm error 금지
• segmetation fault, bus error, double free 금지
• heap에 동적 할당된 메모리 해제 (메모리 누수 방지)
• Makefile 제출
  • -Wall -Wextra -Werror 플래그 지정
  • relink 금지 (다시 make했을 때 재실행 금지)
  • $(NAME), all, clean, fclean, re 규칙 포함
• libft 사용
  • 소스와 Makefile을 libft 폴더에 복사해야함
  • 프로젝트 Makefile은 libft의 Makefile을 사용하여 라이브러리를 컴파일한 다음, 프로젝트 컴파일 해야함
• 전역 변수 금지

📒 Mandatory part

📕 정의

1) Rule

• Stack A : 랜덤한 개수의 양의 정수와 음의 정수 (중복된 값 없음)
• Stack B : 비어있음
• 스택 A에 오름차순으로 정렬

2) Instruction

• sa (swap a) : 스택 a의 top에 위치한 2개의 원소 순서 바꿈
• sb (swap b) : 스택 b의 top에 위치한 2개의 원소 순서 바꿈
  • 스택 a/b가 비어있거나 원소가 1개일 경우 아무 동작X
• ss : sa + sb 동시에 수행
  
  
• pa (push a) : 스택 a의 top에 위치한 원소 1개를 스택 b의 top으로 옮김
• pb (push b) : 스택 b의 top에 위치한 원소 1개를 스택 a의 top으로 옮김
  • 스택 a/b가 비어있을 경우 아무 동작X
    
    
• ra (rotate a) : 스택 a의 원소를 1칸씩 위로 옮김
• rb (rotate b) : 스택 b의 원소를 1칸씩 위로 옮김
  • 스택의 첫 번째 원소는 맨 마지막에 위치
• rr : ra + rb 동시에 수행
  
  
• rra (reverse rotate a) : 스택 a의 원소를 1칸씩 아래로 옮김
• rrb (reverse rotate b) : 스택 b의 원소를 1칸씩 아래로 옮김
  • 스택의 마지막 원소는 맨 처음에 위치
• rrr : rra + rrb 동시에 수행

3) Example

• 랜덤한 정수 배열 정렬 (두 스택 a, b 모두 오른쪽으로 크기가 증가)
• 스택 a의 정수를 12개의 명령어로 정렬

Init a and b:
2
1
3
6
5
8
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec sa:
1
2
3
6
5
8
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec pb pb pb:
6 3
5 2
8 1
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec ra rb (equiv. to rr):
5 2
8 1
6 3
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec rra rrb (equiv. to rrr):
6 3
5 2
8 1
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec sa:
5 3
6 2
8 1
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec pa pa pa:
1
2
3
5
6
8
_ _
a b
----------------------------------------------------------------------------------------------------------

4) Description

• 스택 a에 들어갈 정수의 목록을 인자값으로 받기
  • 첫 번째로 들어오는 인자가 스택의 맨 위에 옴
  • 매개변수가 지정되지 않은 경우, 프로그램은 아무것도 표시하지않고 prompt 반환
• 스택 a를 오름차순으로 정렬
  • 가능한 적은 개수의 명렁어 사용
  • 사용한 명령어의 목록을 마지막에 출력
  • 명령어는 '\n'으로만 구분되어 출력
• 가능한 적은 개수의 명령어로 정렬
  • 사용한 명령어의 개수와 최대 명령어의 개수를 비교
• 오류가 발생시, 표준 출력으로 Error와'\n' 출력
  • 특정 인자값이 정수가 아닐 경우
  • 정수보다 큰 인자값이 들어올 경우
  • 중복된 인자가 들어오는 경우

  $>./push_swap 2 1 3 6 5 8
sa
pb
pb
pb
sa
pa
pa
pa
$>./push_swap 0 one 2 3
Error
$>

• 평가시 프로그램을 확인하기 위해 binary 제공됨
  • checker_OS 프로그램이 'KO' 출력할 경우, 출력한 명령어 리스트가 정수 배열 정렬에 실패

    $>ARG="4 67 3 87 23"; ./push_swap $ARG | wc -l
    6
    $>ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker_OS $ARG
    OK
    $>