주인장이 귀찮아서 천천히 할 예정입니다

과제 설명

push_swap

터미널에
./push_swap "3 2 5 8 7" 1 0 "15 79"
등 숫자를 입력하면 해당 숫자들을 stack a에 저장한 후 stack b를 활용하여 해당 숫자들을 sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr 만을 활용하여 정렬해야 한다.

• sa (swap a): a의 최상위에 있는 인자 두 개를 바꾼다.
• sb (swap b): b의 최상위에 있는 인자 두 개를 바꾼다.
• ss : sa와 sb를 동시에 실행한다.
• pa (push a): b의 최상위 인자를 a의 최상위로 보낸다.
• pb (push b): a의 최상위 인자를 b의 최상위로 보낸다.
• ra (rotate a): a의 최상위 인자를 a의 마지막으로 보낸다.
• rb (rotate b): b의 최상위 인자를 b의 마지막으로 보낸다.
• rr : ra와 rb를 동시에 실행한다.
• rra (reverse rotate a): a의 마지막 인자를 a의 최상위로 보낸다.
• rrb (reverse rotate b): b의 마지막 인자를 b의 최상위로 보낸다.
• rrr : rra와 rrb를 동시에 실행한다.

필자는 stack a와 stack b를 양방향 리스트로 구현하고
알고리즘은 모래시계 알고리즘을 사용했다.

사용한 구조체들

 typedef struct s_info
{
	int			str_cnt;		//인자로 넣은 숫자들의 갯수
	int			parse_cnt;
	int			*num_arr;		//인자로 넣은 숫자들 배열
}				t_info;

typedef struct s_node	//양뱡향 리스트
{
	int				num;
	struct s_node	*next;
	struct s_node	*prev;
}				t_node;

typedef struct s_stack {
	int		len;
	t_node	*head;
	t_node	*tail;
}				t_stack;

typedef struct s_ps
{
	t_stack	*a;		//a스택
	t_stack	*b;		//b스택
	t_stack	*cmd_stack;	//ra, rb 등등 명령어가 저장될 스택
	int		cmd_cnt;	//저장된 명령어 갯수
}				t_ps;

main 문

int	main(int ac, char **av)
{
	t_info	info;
	t_ps	ps;
	int		chunk;

	init_info(&info, ac, av);	//info 구조체 내부 인자 배열에 숫자들 넣는 함수
	init_ps(&info, &ps);	//해당 인자들 정렬한 배열을 만들고 기존 비정렬 배열과 비교해 인덱스 번호를 딴 배열을 만드는 함수 -> 모래시계 알고리즘을 사용하기 위해 인덱스 번호를 딴 배열은 꼭 필요함
	if (check_sort(&ps))	//정렬이 되어있는지 확인, 정렬이 되어있다면 free 후 코드 종료
	{
		free_ps(&ps);
		free_exit(&info);
	}
	chunk = get_chunk(ps.a->len);	//모래시계 알고리즘을 효율적으로 하기 위해 필요한 덩어리 값(chunk) 구하는 함수
	if (info.str_cnt < 6)	//인자가 5개 이하일 경우 인자 갯수에 비해 명령의 수(ra,rb, ...)의 갯수가 너무 많으므로 과제 조건을 맞추기 위한 하드코딩
		sort_under_5(&ps);
	else
	{
		a_to_b(&ps, 0, chunk);	//a인자들 모두 b로 보냄(모래시계)
		b_to_a(&ps);	//모든 인자들에서 가장 큰 값을 a로 보냄
	}
	rr_rrr_check(&ps);	//rr이나 rrr이 나오는 경우를 확인 후 바꿈
	print_all_cmd(ps.cmd_stack);	//모든 명령들 출력
	free(info.num_arr);
	free_ps(&ps);
	return (0);
}

우선 모래시계 알고리즘은 a의 모든 인자들을 b로 보낸 후 b에서 가장 큰 값을 b스택의 최상위로 올려 a로 보내며 정렬을 한다. 따라서 인자가 아무리 적어도 명령의 갯수가 인자 * 2배이므로 인자가 5개일 때 최솟값이 10개이다. 따라서 과제가 원하는 명령의 수를 충족하려면 5개 이하 인자일 때 하드코딩을 통해 따로 처리해주어야 한다.