<aside> ⚠️ 유의사항

• 전역 변수 금지
• 첫 번째 인수는 스택의 맨 위에 있어야 한다.
• 제공된 바이너리와 똑같은 동작을 재현할 필요는 없다. 오류 관리는 필수지만 인수를 구문 분석하는 방법을 결정하는 것은 사용자에게 달려 있다. </aside>

구현 순서

필요 조건

• push_swap : 스택 정렬

  Program name	push_swap
  Turn in files	Makefile, *.h, *.c
  Makefile	NAME, all, clean, fclean, re
  Arguments	stack a: A list of integers
  External functs.	read, write, malloc, free, exit
  • ft_printf and any equivalent YOU coded
  Libft authorized	Yes
  Description	Sort stacks

• checker : 정렬 명령어 실행

  Program name	checker
  Turn in files	.h, *.c
  Makefile	bonus
  Arguments	stack a: A list of integers
  External functs.	read, write, malloc, free, exit
  • ft_printf and any equivalent YOU coded
  Libft authorized	Yes
  Description	Execute the sorting instructions

공통 부분 - 구문 분석

• 실행파일은 INT_MIN ~ INT_MAX 범위의 중복없는 임의의 숫자를 인자로 받는다.

  • 입력값으로 받은 첫번째 인수는 스택의 맨 위에 있어야한다.

• 정수가 아니거나 중복인 경우 “Error\n”을 출력한다.

  $ ./push_swap 3 2 2 4 | cat -e    # 중복 에러
  Error$
  
  $ ./push_swap 3 2 2147483648 | cat -e  # INT 범위를 초과한 경우
  Error$
  
  $ ./push_swap 3 2 one | cat -e  # 정수가 아닌 경우
  Error$
  
  $ ./push_swap "" 1 | cat -e  # 정수가 아닌 경우
  Error$
  

• [참고] 두 실행파일의 main 구조

공통 부분 - 명령어

| pa (push a) | b의 맨 위에 있는 첫 번째 요소를 가져와서 a의 맨 위에 놓는다. b가 비어 있으면 아무 것도 하지 않는다. | | --- | --- | | pb (push b) | a의 맨 위에 있는 첫 번째 요소를 가져와서 b의 맨 위에 놓는다. a가 비어 있으면 아무 것도 하지 않는다. | | ss | sa와 sb를 동시에 사용한다. |

| sb (swap b) | 스택 b의 맨 위에 있는 처음 2개의 요소를 교환한다. 요소가 하나만 있거나 없는 경우 아무 작업도 수행하지 않는다. | | rr | ra와 rb를 동시에 사용한다. | | ra (rotate a) | 스택 a의 모든 요소를 1만큼 위로 이동한다. (첫 번째 요소가 마지막 요소로) | | ra (rotate a) | 스택 b의 모든 요소를 1만큼 위로 이동한다. (첫 번째 요소가 마지막 요소로) | | rrr | rra와 rrb를 동시에 사용한다. | | rra (reverse ra) | 스택 a의 모든 요소를 1만큼 아래로 이동한다. (마지막 요소가 첫 번째 요소로) | | rrb (reverse rb) | 스택 b의 모든 요소를 1만큼 아래로 이동한다. (마지막 요소가 첫 번째 요소로) |

스택 구현

• 2개의 스택 a 및 b 가 존재한다.
• 첫번째 요소와 마지막 요소에 대한 삽입/삭제가 용이해야 하므로, 자료구조는 deque를 추천한다.
  • array : 인덱스 계산 필요
  • linked list : 마지막 요소 접근에 시간이 오래 걸림
  • double linked list : 간단하게 구현 가능

typedef struct s_stack      t_st;

struct s_stack_node
{
		int 				 	 	 	 		num;   // 입력된 인자값 
		unsigned int  	 	 		idx;   // 입력된 전체 값에서의 순서
		struct s_stack_node 	*prev;
		struct s_stack_node 	*next;	
};

struct s_stack
{
		unsigned int					cnt;      // 현재 스택의 개수
		struct s_stack_node	 	*node[2]; // 노드의 시작과 끝을 저장
};

struct s_pushswap
{
		unsigned int			cnt;     // 전체 스택의 사이즈
		struct s_stack	 	a;
		struct s_stack	 	b;
};

enum e_rear
{
		FRONT = 0,
		REAR = 1
}

스택 조작