[push_swap] Day 08. arg가 3개, 5개일 때

jongeun·2021년 5월 29일
3

push-swap

목록 보기
8/10

arg가 3개일 때

평가표에 3개일 때, 5개일 때 몇 개를 넘지 않아야 하는지가 나와 있다.
다들 3개랑 5개일 경우에는 따로 처리하라고 했다. 그래서 따로 코드를 작성했다.

스택에 arg가 3개만 들어왔을 경우에는 평가표에 따르면 최대 2번까지만 기능을 동작시켜서 정렬해야 한다.
이때는 경우의 수가 6개니까 그냥 조건을 다 따져서 처리하면 된다.

방법

  1. arg 3개 중 minmax를 찾는다.

  2. min 값을 가진 노드가 어디에 위치하는지를 먼저 찾고, 다시 경우를 나눈다.
    2-1. a->top->valuemin인 경우
    2-2. a->top->next->valuemin인 경우
    2-3. a->bottom->valuemin인 경우

  3. 위의 세 가지 경우에 대해 각각 max 값을 가진 노드는 어디에 위치하는지 찾는다.

  4. 각각의 경우에 맞게 적절하게 sa, ra, rra를 하면 끝~!

멤췌!

그런데 생각해보니까 정렬을 하던 중에 3개만 정렬해야 할 때 있잖아요?
그때는 막 bottom이랑 비교하면 안 되고, 처음에 rrarrb를 해버리면 안 되고 그런 문제가 있으니까 그건 또 따로 짜줘야 했다.
처음에 위에서 짠 코드를 이런 경우에서도 그대로 적용시켜서 이상하게 나왔었다. 으이구 인간아 ᕙ( ︡’︡益’︠)ง
그래서 그냥 그것도 경우 6개 다 따로 짰다.

arg가 5개일 때

스택에 arg가 5개만 들어왔을 경우에는 평가표에 따르면 최대 12번까지만 기능을 동작시켜서 정렬해야 한다.
이때는 경우의 수가 좀 더 많아지고 조건을 다 따지기엔 복잡하니까 방법을 좀 달리했다.

방법

(마지막 날에 수정함)

  1. arg 5개 중 mid를 찾는다.

  2. 스택 b에 노드가 2개 쌓일 때까지만 반복문을 돌린다. int형 변수 pb를 만들어서 pb를 몇 번 했는지 세고 그게 2가 되면 반복문을 빠져 나오게 했다.

  3. 만약 a->top->valuemid보다 작으면 pb를 하고, mid보다 크거나 같으면 ra로 위로 회전시켜 맨 밑으로 보낸다.

  4. 여기까지 하면 스택 a에는 arg 5개 중 가장 큰 값 3개만 남고, 스택 b에는 가장 작은 값 2개가 들어가있을 것이다.

  5. 이제 스택 a는 위에서 arg가 3개만 들어왔을 때 사용한 함수를 호출해서 정렬해준다.

  6. 스택 b는 arg가 2개일 때 사용한 함수를 호출해서 정렬하고 pa를 한다.

정렬 끝~!


마무리

일단 이번 글은 여기까지. 5개일 때 조건을 다 따져야 하나..? 싶어서 순간 막막하고 하기 싫어졌었는데, hyunlee님께 조언을 얻어서 해결할 수 있었다. 👍🏻

사실 코드도 이미 거의 다 짰음. 이제 최적화만 하면 된다. 룰루랄라

profile
It's me, jkeum!

0개의 댓글