push-swap

coh·2023년 2월 28일

push swap

push-swap

push-swap과제..

데이터를 정렬하는 알고리즘 프로젝트.

정렬할 integer들과 두 개의 stack, 명령어들의 집합이 주어짐.
->최소한의 명령어들을 이용하여 정수형 인자를 정렬하고 최종적으로 표준 출력.
->복잡도 고려

solving

sorting 후 2피봇 지정. 데이터를 3분할
greedy알고리즘 적용.

deque STRUCTURE만들기

void	deque_init(t_deque *deque)
{
	deque->cnt = 0;
	deque->top = 0;
	deque->bottom = 0;
}

void	append(t_deque *deque, int data)
{
	t_node	*node;

	node = (t_node *)malloc(sizeof(t_node));
	node->next = 0;
	node->prev = 0;
	node->data = data;
	if (is_empty(deque))
		deque->top = node;
	else
	{
		node->prev = deque->bottom;
		deque->bottom->next = node;
	}
	deque->bottom = node;
	deque->cnt++;
}

int	pop_left(t_deque *deque)
{
	t_node	*ptr;
	int		data;

	if (is_empty(deque))
		print_emsg("Error\n");
	ptr = deque->top;
	data = ptr->data;
	if (deque->cnt == 1)
	{
		deque->top = 0;
		deque->bottom = 0;
	}
	else
	{
		deque->top = ptr->next;
		deque->top->prev = 0;
	}
	deque->cnt--;
	free(ptr);
	return (data);
}

void	append_left(t_deque *deque, int data)
{
	t_node	*node;

	node = (t_node *)malloc(sizeof(t_node));
	node->next = 0;
	node->prev = 0;
	node->data = data;
	if (is_empty(deque))
		deque->bottom = node;
	else
	{
		node->next = deque->top;
		deque->top->prev = node;
	}
	deque->top = node;
	deque->cnt++;
}

int	pop(t_deque *deque)
{
	t_node	*ptr;
	int		data;

	if (is_empty(deque))
		print_emsg("Error\n");
	ptr = deque->bottom;
	data = ptr->data;
	if (deque->cnt == 1)
	{
		deque->top = 0;
		deque->bottom = 0;
	}
	else
	{
		deque->bottom = ptr->prev;
		deque->bottom->next = 0;
	}
	deque->cnt--;
	free(ptr);
	return (data);
}

첨에 그냥 만들다가 나중에 명령어 에러뜨길래 왜 뜨지 싶어서 찾아보니 pop, pop_left에서 데이터 갯수가 1일 때 처리를 덜 해줘서 segmentation에러가 발생함

greedy.c 의 주석

// greedy알고리즘이 시작되는 부분.
// 스택 b의 모든 원소에 대해 스택a로 보낼 때 가장 명령어를 적게 사용하는 스택b를 찾는다.
// ex)
// stack a : 3 1 2
// stack b : 7 14

// case 1)7을 넣는 경우
// stack a : 1 2 3
// stack b : 7 14
// ->ra
// stack a : 7 1 2 3
// stack b : 14
// ->pa

// case 2) 14를 넣는 경우
// stack a : 1 2 3
// stack b : 14 7
// ->ra rb
// stack a : 14 1 2 3
// stack b : 7
// ->pa

// 따라서 7을 넣는 것이 가장 적은 명령어를 사용하게 된다. (물론 rr을 하면은 한 번이지만 명령어 수를 가장 적게 사용하는 b를 고르는 것이 greedy의 핵심)
// 그래서 find_min()는 현재 stack b의 데이터를 넣게되면
// stack a에서 명령어를 몇 번 할 것인지(a_location = get_loc_a())와 stack b에서 명령어를 몇 번 할 것인지(=b_location)의
// 갯수를 찾아주고 가장 작게 명령어를 움직이는 경우를 찾아서(cmp_location()) da와 db에 담아준다.