[push_swap] Day 04. 동작할 기능 만들기 & 중복 인자 체크

jkeum·2021년 5월 24일

Sort algorithm push_swap

push-swap

목록 보기

4/10

동작할 기능 만들기

구현해야 할 기능

프로그램을 동작시키기 위해 구현해야 할 기능들이다.

sa: swap a - a의 가장 위에 있는 두 요소를 교환한다. (요소가 하나도 없거나 한 개만 있을 때는 아무것도 수행하지 않는다.)
sb: swap b - b의 가장 위에 있는 두 요소를 교환한다. (요소가 하나도 없거나 한 개만 있을 때는 아무것도 수행하지 않는다.)
ss: sa와 sb를 동시에 수행한다.
pa: push a - b의 가장 위에 있는 요소를 a의 가장 위에 넣는다. (b가 비었을 때는 아무것도 수행하지 않는다.)
pb: push b - a의 가장 위에 있는 요소를 b의 가장 위에 넣는다. (a가 비었을 때는 아무것도 수행하지 않는다.)
ra: rotate a - a의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막 요소가 된다.
rb: rotate b - b의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막 요소가 된다.
rr: ra와 rb를 동시에 수행한다.
rra: reverse rotate a - a의 모든 요소를 1만큼 아래로 이동시킨다. 마지막 요소는 첫 번째 요소가 된다.
rrb: reverse rotate b - b의 모든 요소를 1만큼 아래로 이동시킨다. 마지막 요소는 첫 번째 요소가 된다.
rrr: rra와 rrb를 동시에 수행한다.

Swap

먼저 sa, sb, ss를 구현하기로 했다.

스택에 노드가 두 개 이상 존재할 때만 기능이 동작하고, 하나만 있거나 하나도 없을 때는 아무 것도 실행하지 않으면 된다.

t_node형의 temp 변수와 top_next를 선언해서 temp에는 stack->top을, top_next에는 stack->top->next를 넣고 두 위치를 바꿔서 연결했다.

원래 temp에 stack->top만 넣고 적절히 next와 prev를 바꿔서 연결하려고 했는데, 계속 헷갈려서 변수를 두 개 선언했다. 결국 top_next는 한 번밖에 안 쓰긴 했는데 잘 동작하는 것을 확인하고 그걸 없애서 실행해보니까 잘 동작하지 않았다. 이유는? 모릅니다.

main()을 작성해서 확인해보니까 노드가 두 개 있었을 경우에는 stack->bottom을 다시 지정해줘야 했다. 그래서 그 조건을 추가했다.

그리고 ss는 함수에 넣는 인자를 다르게 해서 두 번 실행하면 되는데, 생각해보니 하나의 기능이 동작할 때마다 그 동작을 출력해줘야 한다.
만약 sa(혹은 sb)를 하는 함수에서 sa(혹은 sb)를 출력해주고 ss를 하는 함수에서 함수를 두 번 호출한 다음에 ss를 출력하게 되면, sa와 sb와 ss가 다 출력될 것이다.
그리고 어차피 sa와 sb도 함수를 따로 나누지 않았기 때문에 어떤 스택을 swap할 것인지 구별해야 했다.
그래서 생각한 방법이 인자에 flag를 추가로 넣어주는 것이다.
숫자로 쓰면 헷갈릴 수 있으니까 structures.h 에 매크로 변수를 선언해서 사용하기로 했다.

# define A 1
# define B 2
# define ALL 3

이렇게 작성해서 조건문을 사용해서 sa나 sb, 혹은 ss를 출력하게 했다.

Push

이번에는 pa, pb를 구현했다.

스택에 노드가 한 개 이상 존재할 때만 동작하고, 하나도 없을 때는 아무것도 실행하지 않으면 된다.

이전에 작성했던 push_pop()을 그대로 사용했다.
대신 그 함수 안에 있던, 노드가 한 개 이상인지 확인해서 하나도 없으면 그냥 리턴하는 그 조건문만 밖으로 빼왔다.
flag를 확인해서 pa나 pb를 출력하는 작업이 실행되면 안 되기 때문이다.

Rotate

ra, rb, rr을 구현했다.

스택에 노드가 두 개 이상 존재할 때만 동작하고, 하나도 없을 때는 아무것도 실행하지 않으면 된다.

stack->top을 stack->bottom으로 옮겨주고 연결을 잘 해줘야 했다.
swap에서 했던 것처럼 t_node형의 temp와 top_next 변수를 선언해서 temp에는 stack->top을, top_next에는 stack->top->next를 넣었다.
stack->bottom->next에 temp를 연결하고 그 다음에 temp->prev를 stack->bottom으로 연결했다.
temp->next는 NULL로 설정했다.
그리고 다시 stack->bottom을 temp로 설정했다.

이제 stack->top을 top_next로 연결하고 그 다음에 stack->top->prev를 NULL로 설정했다.

마지막으로 flag를 확인해서 ra, rb 혹은 rr을 출력하게 했다.

Reverse Rotate

rra, rrb, rrr을 구현했다.

역시 스택에 노드가 두 개 이상 존재할 때만 동작하고, 하나도 없을 때는 아무것도 실행하지 않으면 된다.

이번에는 stack->bottom을 stack->top으로 옮겨주고 연결을 잘 해줘야 했다.
rotate와 비슷하게 t_node형의 temp와 bottom_prev 변수를 선언해서 temp에는 stack->bottom을, bottom_prev에는 stack->bottom->prev를 넣었다.
stack->top->prev에 temp를 연결하고 그 다음에 temp->next를 stack->top으로 연결했다.
temp->prev는 NULL로 설정했다. 그리고 다시 stack->top을 temp로 설정했다.

이제 stack->bottom을 bottom_prev로 연결하고 그 다음에 stack->bottom->next를 NULL로 설정했다.

마지막으로 flag를 확인해서 rra, rrb 혹은 rrr을 출력하게 했다.

중복 인자 체크

생각해보니 중복된 수가 들어왔을 때 Error를 출력하고 끝내야 하는데 그 처리를 안 했다.
중복된 수가 들어왔는지 확인하는 check_duplicate() 함수를 작성했다.

이 함수는 일단 스택 리스트를 만들고 난 다음에 실행된다.
만약 인자로 10 42 29 +42 이렇게 들어왔다면, 42 와 +42 는 같은 수라서 중복이다.
그런데 문자열 상태에서 ft_strcmp(42, +42) 이런 식으로 검사를 하게 된다면 같지 않다고 리턴될 것이다.
그래서 리스트가 다 만들어진 다음에 앞에서부터 검사했다.

예를 들어, 인자로 1 3 5 3 7 이 들어왔다고 하자. 먼저 맨 앞의 1 부터 검사한다.
t_node형의 temp 변수를 선언해서 여기에는 a->next를 담아준다.(처음에는 스택 a에만 리스트가 생성되어서 스택 a만 검사하면 되니까 이름을 a라고 함)
int형 cur_value에는 a->value가 담긴다. 현재 cur_value는 1 이다.
그리고 temp를 끝까지 넘기면서 cur_value와 같은 수가 있는지 검사한다.
중복되는 숫자가 없으므로 a를 a->next로 바꿔준다.
이제 두 번째 인자로 들어온 3 을 검사한다. cur_value는 3 이다.
temp는 다시 a->next가 되고, temp를 끝까지 넘기면서 cur_value와 같은 수가 있는지 검사한다.
이번에는 중복된 숫자가 존재하므로 print_error()를 호출해서 Error 메세지를 출력하고 프로그램을 종료한다.