배열로 push_swap 해보자! (6)
“push_swap에 대하여”
- 명령어 구현하기
- 1. SA, void do_sa(t_deque *a)
- 2. SB, void do_sb(t_deque *b)
- 3. SS, void do_ss(t_deque *a, t_deque *b)
- 4. PA, void do_pa(t_deque *a, t_deque *b)
- 5. PB, void do_pb(t_deque *a, t_deque *b)
- 6. RA, void do_ra(t_deque *a)
- 7. RB, void do_rb(t_deque *b)
- 8. RR, void do_rr(t_deque *a, t_deque *b)
- 9. RRA, void do_rra(t_deque *a)
- 10. RRB, void do_rrb(t_deque *b)
- 11. RRR, void do_rrr(t_deque *a, t_deque *b)
- 그 외의 중요한 함수
명령어 구현하기
- 추상화된 pop, push, rotate 명령어 함수들을 이해했다면, 여기는 너무너무너무 쉬워서 눈물을 흘릴 지경이 된다. 맞다. 이러려고 배열로 push swap한거다.
1. SA, void do_sa(t_deque *a)
void do_sa(t_deque* a)
{
write(1, "sa\n", 3);
swap_top(a);
}
물론 출력하는 것과 명령어 함수를 실행하는 것의 순서 차이는 없다.
swap_top(a)을 실행하고 sa를 출력한다. 여기까지 따라왔다면, 내부 구현에 대해선 알 것이라 생각한다. 추상화에 대해 기억할 것이다. 물론 내부 구현은 알고 있어야 한다.
2. SB, void do_sb(t_deque *b)
void do_sb(t_deque* b)
{
write(1, "sb\n", 3);
swap_top(b);
}
- swap_top(b)을 실행하고 sb를 출력한다.
3. SS, void do_ss(t_deque *a, t_deque *b)
void do_sb(t_deque *a, t_deque *b)
{
write(1, "ss\n", 3);
swap_top(a);
swap_top(b);
}
- swap_top(a), swap_top(b)을 실행하고 ss를 출력한다.
4. PA, void do_pa(t_deque *a, t_deque *b)
void do_pa(t_deque *a, t_deque *b)
{
write(1, "pa\n", 3);
push(b, a);
}
- b에서 a로 push하는 push 함수를 출력하고, pa를 출력한다.
5. PB, void do_pb(t_deque *a, t_deque *b)
void do_pa(t_deque *a, t_deque *b)
{
write(1, "pb\n", 3);
push(a, b);
}
- a에서 b로 push하는 push 함수를 출력하고, pb를 출력한다.
6. RA, void do_ra(t_deque *a)
void do_ra(t_deque *a)
{
write(1, "ra\n", 3);
rotate(a);
}
- a의 원소를 회전시키는 rotate 함수를 실행시키고, ra를 출력한다. 물론 첫 번째 원소는 마지막 원소가 된다.
7. RB, void do_rb(t_deque *b)
void do_rb(t_deque *b)
{
write(1, "rb\n", 3);
rotate(b);
}
- b의 원소를 회전시키는 rotate 함수를 실행시키고, rb를 출력한다. 물론 첫 번째 원소는 마지막 원소가 된다.
8. RR, void do_rr(t_deque *a, t_deque *b)
void do_rr(t_deque *a, t_deque *b)
{
write(1, "rr\n", 3);
rotate(a);
rotate(b);
}
- a와 b를 모두 rotate 시키고 rr을 출력한다.
9. RRA, void do_rra(t_deque *a)
void do_rra(t_deque *a)
{
write(1, "rra\n", 4);
reverse_rotate(a);
}
- a의 원소를 회전시키는 reverse rotate 함수를 실행시키고, rra를 출력한다. 물론 마지막 원소는 첫 번째 원소가 된다.
10. RRB, void do_rrb(t_deque *b)
void do_rrb(t_deque *b)
{
write(1, "rrb\n", 4);
reverse_rotate(b);
}
- b의 원소를 회전시키는 reverse rotate 함수를 실행시키고, rrb를 출력한다. 물론 마지막 원소는 첫 번째 원소가 된다.
11. RRR, void do_rrr(t_deque *a, t_deque *b)
void do_rrr(t_deque *a, t_deque *b)
{
write(1, "rrr\n", 4);
reverse_rotate(a);
reverse_rotate(b);
}
- a, b의 원소를 회전시키는 reverse rotate 함수를 각각 실행시키고, rrr를 출력한다.
그 외의 중요한 함수
- 과제를 진행하면서 진짜 중요한 함수 2개가 있었다. 배열로 push swap을 진행하는데 내가 겪었던 애로 사항이 담겨 있는 함수라고 할 수 있다. 이 두 함수에 대해 설명하며 시리즈를 마친다.
(1) void deque_to_arr(t_deque *d, int *a)
void deque_to_arr(t_deque *d, int *a)
{
int i;
i = -1;
while (++i < d->size)
a[i] = front_idx(d, i); // 밑에서 설명하겠다.
}
- t_deque에 담겨 있는 스택을 매개 변수로 받은 정수 배열(a)에 하나씩 넣어서 반환해주는 것이다. 앞에서 봤듯이 우리는 배열의 arr의 head와 tail - 1 인덱스 사이의 원소들만을 스택으로 간주했는데, 그러다보니 스택들이 배열 상에서 생긴게 매우 자유분방했던 것이 기억났을 것이다. 그 자유분방한 모양을 정확하게 배열로 옮기는 것이다. head를 0으로, tail이 size인 예쁜 배열로 바꾸는 함수이다. 예를 들어 …
capacity = 16;
tail
↓
d->arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, -, ... , 11, 10}
↑
head
- 이 스택을 …
int *a = {11, 10, 1, 2, 3, 4, 5, 6, 7, 8}
인 배열로 깔끔하게 도려내서 만들어주는 함수다. 쓰레기 값들도 전부 쳐낸, 그야말로 arr[head]부터 arr[tail - 1]이 처음(arr[0])부터 마지막(arr[size - 1])인 예쁜 배열로 바꿔주는 함수다. 하드 코딩을 할때 요긴하게 썼었던 기억이 난다.
(2) int front_idx(t_deque *deq, int idx)
int front_idx(t_deque *deq, int idx)
{
int i;
i = deq->head;
i += idx;
if (i >= deq->capacity)
i -= deq->capacity;
return (deq->arr[i]);
}
진짜 진짜 진짜 진짜 진짜 중요한 함수였다. 이 함수는 deq에 있는 스택의 idx번째에 있는 원소를 “수학적으로” 반환받는 함수다. 즉 idx를 5로 주면 스택의 5번째에 있는 원소를 반환받는다. 알다시피 구조체 내에 있는 배열의 arr[4]는 스택의 5번째 값이 아니다. 스택의 5번째 값은 arr[head + 4]이며, head는 0에서 capacity - 1 사이의 어떠한 값이든 될 수 있다(물론 head + 4가 capacity 이상일 때의 예외 처리를 해야 한다). 이 함수는 그 장벽을 없애주는 장치다. 더 중요한 것은 인덱스를 “수학적으로” 찾는다는 거다. i를 head로 정하고, idx를 더한 뒤, capacity를 넘었으면 capacity만큼을 빼서 예외 처리를 한다.
수학적으로 찾지 않는다는건, idx를 매개변수로 받아서, arr[head]에서 idx만큼 while문을 돌아서 값을 반환받는다는 것이다. 이게 얼마나 끔찍한 짓인가? 나는 수학적으로 idx 값을 받지 않았다는 것을 과제를 다 만들고 테스터를 돌리면서 알았다. 1000개를 테스트하는데 한 케이스를 처리하는데 수 분의 시간이 걸렸었다(시간 복잡도 살인마…).
시간 복잡도 이야기가 나와서 그런데, “그리디 알고리즘”을 사용해서 push swap을 진행하게 되면, 연결 리스트 대신 배열을 택해서 스택을 구현했다는 점에서 얻은 시간 복잡도의 메리트가 퇴색된다고 생각한다. 그리디 알고리즘 자체가 시간 복잡도를 박살내면서 진행하는 방식이기 때문이다(근데 본인은 그리디로 했다…ㅋㅎ). 물론 과제가 시간 복잡도를 신경쓰지 않고 명령어 횟수를 줄여서 정렬하는 것이 컨셉트이기 때문에 시간 복잡도의 메리트가 퇴색되는 것이 아주 큰 문제는 아니다.
그러니 각자 자기가 좋아하는 알고리즘으로 멋있게 push_swap을 진행해보자!!!
