배열로 push_swap 해보자! (번외)
“push_swap에 대하여”
메모
- push_swap을 진행하면서 내가 남겨놓은 메모가 있다. rotate와 reverse rotate에서 보여준 적이 있는데, 여기에 내가 남겼던 나머지 메모들을 풀어놓는다.
1. push_front
- stack a = {1, 2, 3, 4, 5, 6}에 차례로 7, 8을 push_front하는 과정이다.
2. push_back
- stack a = {7, 1, 2, 3, 4, 5, 6}에 차례로 8, 9를 push_back하는 과정이다. 9을 push할 때, size(8)가 capacity(8)와 동일하여 resize한다.
3. pop_front
- stack a = {7, 1, 2, 3, 4, 5, 6}에 pop_front를 두 번 실행하는 과정이다. stack a는 {2, 3, 4, 5, 6}이 된다.
4. pop_back
- stack a = {2, 3, 4, 5, 6}에 pop_back을 두 번 실행하는 과정이다. stack a는 {2, 3, 4}가 된다.
5. rotate
- 지난 글에서 rotate를 설명할 때 넣지 않은 다른 메모다. stack a = {1, 2, 3, 4, 5, 6}을 rotate하는 과정이다. head를 한칸 옮겨 pop_front하고, 그 pop한 값을 그대로 push_back해서 결과적으로 stack a를 {2, 3, 4, 5, 6, 1}로 만들어놓는다.
6. sort 3
int sort_3(t_deque *deq)
{
int a[3];
deque_to_arr(deq, a);
if (a[0] > a[1])
{
if (a[0] > a[2])
{
do_ra(deq);
if (a[1] > a[2])
do_sa(deq);
}
else
do_sa(deq);
}
else
{
if (a[1] > a[2])
{
do_rra(deq);
if (a[2] > a[0])
do_sa(deq);
}
}
return (0);
}
이건 원소 3개를 하드코딩하는 건데
deque_to_arr(deq, a);로 스택을 배열로 깔끔하게 발라놓고, a[idx]를 하나하나 확인하면서 명령어를 실행한다.deq의 배열과 a의 배열은 원본 <-> 복사본 관계로 sort 3함수에서는 a 배열의 순서만 확인하면서 원본 deq 배열의 순서를 바꿔주기 때문에 a 배열의 순서에 변동을 주지 않으면서 deq를 정렬할 수 있다.
