push_swap 이란 어떠한 저장공간에 있는 데이터를 한정된 명령어를 이용하여 최대한 적은 횟수 내에 정렬하는 것을 목표로 합니다.
-
성공하기 위해서는 저장공간을 만들고, 다양한 정렬 알고리즘을 조작해 보고, 최적화된 데이터 정렬에 가장 적합한 알고리즘을 선택하여야 합니다.
-
과제에서는 정렬해야 하는 int 값들과 두 개의 저장공간, 그리고 이 저장공간을 조작하는 명령어 집합이 주어집니다.
가장 먼저 해야할 명령어 집합과 저장공간의 타입에 대해 알아보고 작성하려합니다.
명령어 집합
sa : swap a - 스택 a의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다. 스택 a가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.
sb : swap b - 스택 b의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다. 스택 b가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.
ss - sa와 sb를 동시에 수행합니다.
pa : push a - 스택 b의 top에 위치한 원소 한 개를 스택 a의 top으로 옮깁니다. 스택 b가 비어있을 경우에는 아무 동작도 하지 않습니다.
pb : push b - 스택 a의 top에 위치한 원소 한 개를 스택 b의 top으로 옮깁니다. 스택 a가 비어있을 경우에는 아무 동작도 하지 않습니다.
ra : rotate a - 스택 a의 원소를 한 칸씩 위로 옮깁니다. 스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
rb : rotate b - 스택 b의 원소를 한 칸씩 위로 옮깁니다. 스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
rr : ra와 rb를 동시에 수행합니다.
rra : reverse rotate a - 스택 a의 원소를 한 칸씩 아래로 옮깁니다. 스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
rrb : reverse rotate b - 스택 b의 원소를 한 칸씩 아래로 옮깁니다. 스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
rrr : rra와 rrb를 동시에 수행합니다.
자료구조
우선 해당 명령어 집합들을 본 순간
1순위 덱
2순위 원형 큐
3순위 스택
으로 작성해야 하겠다고 생각이 났습니다.
간단하게 자료구조에 대해 설명하자면
선형큐 (queue)
FIFO (First In First Out) 형식
기본적인 큐의 형태로 먼저 들어온 인자가 먼저 나가는 방식으로 놀이공원 대기줄 과 같은 형식이라 생각하시면 이해하기 쉽습니다.
원형큐 (queue)
저장공간을 원형큐로 작성하면 rr / rrr 명령어시 'front와 last위치만 앞뒤로 조절하면 쉬울거 같다.' 라고 생각하여 2순위로 놓았습니다.
스택 (stack)
LIFO (Last In First Out) 형식으로 스택으로도 저장공간을 만들 수 있지만, rr / rrr 명령어 처리시 bottom값을 알기가 어려워 굳이 스택으로 해야할까? 라는 생각으로 3순위에 놓았습니다.
덱 (deque)
덱은 double-ended queue의 줄임말입니다.
큐의 앞, 뒤 모두에서 삽입 및 삭제가 가능한 큐를 의미하기 때문에 큐나 스택보다는 유연한 동작을 한다 생각하시면 될 거 같습니다.
앞 뒤 모두 인자를 빼고 넣는 명령어들이 있기 때문에 자연스레 덱으로 짜야겠다 느껴져 1순위에 놓았습니다.
그럼 덱으로 짜야한다고 마음을 먹고 덱을 구현해보겠습니다.
덱 구현
typedef struct s_node
{
int data;
struct s_node *prev;
struct s_node *next;
} t_node;
typedef struct s_stack
{
int size;
struct s_node *top;
struct s_node *bottom;
} t_stack;처음에 subject에서 stack이라 명시하여 생각없이 구조체 명을 stack이라 작성했습니다.
두개의 구조체중 t_node에는 int형 data와 prev, next노드의 정보를 가지고 있습니다.
t_stack에는 덱의 size, top노드의 정보, bottom노드의 정보를 담고 있습니다.
t_stack *stack_init(void)
{
t_stack *stack;
stack = malloc(sizeof(t_stack));
if (stack == NULL)
return (0);
stack->top = NULL;
stack->bottom = NULL;
stack->size = 0;
return (stack);
}덱 자료구조를 생성 해줍니다.
t_node *getnode(int data)
{
t_node *new;
new = malloc(sizeof(t_node));
if (new == NULL)
return (0);
new->data = data;
new->next = NULL;
new->prev = NULL;
return (new);
}안에 들어갈 노드도 생성하는 함수를 작성해줍니다.
덱은 top에서도 bottom에서도 노드를 push하고 pop을 해줘야 하기 때문에 총 4개의 함수를 작성해줍니다.
void push_top(t_stack *list, int data)
{
t_node *new;
t_node *oldtop;
new = getnode(data);
if (list->top == NULL)
{
list->top = new;
list->bottom = new;
}
else
{
oldtop = list->top;
oldtop->next = new;
new->prev = oldtop;
list->top = new;
}
list->size++;
}
void pop_top(t_stack *list)
{
t_node *nowtop;
t_node *newtop;
nowtop = list->top;
if (nowtop == NULL)
return ;
else if (list->size == 1)
{
list->top = NULL;
list->bottom = NULL;
}
else
{
newtop = list->top->prev;
newtop->next = NULL;
list->top = newtop;
}
list->size--;
free (nowtop);
}
void push_bottom(t_stack *list, int data)
{
t_node *new;
t_node *oldbottom;
new = getnode(data);
if (list->bottom == NULL)
{
list->top = new;
list->bottom = new;
}
else
{
oldbottom = list->bottom;
oldbottom->prev = new;
new->next = oldbottom;
list->bottom = new;
}
list->size++;
}
void pop_bottom(t_stack *list)
{
t_node *nowbottom;
t_node *newbottom;
nowbottom = list->bottom;
if (nowbottom == NULL)
return ;
else if (list->size == 1)
{
list->top = NULL;
list->bottom = NULL;
}
else
{
newbottom = list->bottom->next;
newbottom->prev = NULL;
list->bottom = newbottom;
}
list->size--;
free (nowbottom);
}push했을때 덱이 비어있을경우 새 노드를 top과 bottom이라 지정해주고, 기존 old top과 old bottom을 잘 연결해줍니다.
pop했을 경우 덱이 비어있을땐 동작하지 않게 처리하고, 1개만 있을경우에는 top과 bottom에 NULL값을 넣어주고, 그 외에 경우에는 top과 bottom 이전값을 top 또는 bottom으로 지정해주고 free() 처리 하여 메모리 누수를 방지해줍니다.
void sa(t_stack *a)
{
int tmp;
if (a->size < 2)
return ;
tmp = a->top->data;
a->top->data = a->top->prev->data;
a->top->prev->data = tmp;
write(1, "sa\n", 3);
}
void pa(t_stack *a, t_stack *b)
{
if (b->size == 0)
return ;
push_top(a, b->top->data);
pop_top(b);
write(1, "pa\n", 3);
}
void rr(t_stack *a, t_stack *b)
{
if (a->size < 2 || b->size < 2)
return ;
push_bottom(a, a->top->data);
pop_top(a);
push_bottom(b, b->top->data);
pop_top(b);
write(1, "rr\n", 3);
}
void rrr(t_stack *a, t_stack *b)
{
if (a->size < 2 || b->size < 2)
return ;
push_top(a, a->bottom->data);
pop_bottom(a);
push_top(b, b->bottom->data);
pop_bottom(b);
write(1, "rrr\n", 4);
}명령어들은 덱을 짜며 만든 pop, push함수를 활용하여 동작하게 만들어줍니다.
