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

jongeun·2021년 5월 24일
3

push-swap

목록 보기
4/10
post-thumbnail

동작할 기능 만들기

구현해야 할 기능

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

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

Swap

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

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

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

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

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

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

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

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


Push

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

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

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


Rotate

ra, rb, rr을 구현했다.

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

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

이제 stack->toptop_next로 연결하고 그 다음에 stack->top->prevNULL로 설정했다.

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


Reverse Rotate

rra, rrb, rrr을 구현했다.

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

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

이제 stack->bottombottom_prev로 연결하고 그 다음에 stack->bottom->nextNULL로 설정했다.

마지막으로 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라고 함)
intcur_value에는 a->value가 담긴다. 현재 cur_value1 이다.
그리고 temp를 끝까지 넘기면서 cur_value와 같은 수가 있는지 검사한다.
중복되는 숫자가 없으므로 aa->next로 바꿔준다.
이제 두 번째 인자로 들어온 3 을 검사한다. cur_value3 이다.
temp는 다시 a->next가 되고, temp를 끝까지 넘기면서 cur_value와 같은 수가 있는지 검사한다.
이번에는 중복된 숫자가 존재하므로 print_error()를 호출해서 Error 메세지를 출력하고 프로그램을 종료한다.


마무리

리스트의 노드들 연결을 이렇게 저렇게 바꾸는 게 헷갈리고 어려울 것 같았는데 생각보다 금방했다.
헷갈리긴 했는데,, 이렇게 하는 게 좋은 방법인지도 잘 모르겠는데,, 일단은 되니까,,
이제 알고리즘 짜야 한다. 으

profile
It's me, jkeum!

0개의 댓글