[push_swap] Day 05. 알고리즘 만들기

jkeum·2021년 5월 25일
3

push-swap

목록 보기
5/10
post-thumbnail

알고리즘 생각해보기

테스트 케이스로 생각해보기

직접 6-7개의 숫자를 가지고 테스트를 해봤다. 어떤 상황에서 어떤 과정이 공통적으로 들어가는지를 보려고 했다.
테스트를 몇 번 해보면서 일단은 다음과 같은 변수들을 만들면 좋겠다는 생각을 했다.
스택에 들어온 인자들의 최대값(max), 중간값(짝수개라면 큰 쪽 mid), 그리고 최소값(min)을 저장해두는 것이다.

그리고 생각한 조건들은, stack->top->valuemax라면 무조건 ra를 한다.
stack->bottom->valuemid 보다 작다면 rra를 한다.
stack->top->valuemid 보다 작다면 pb를 한다.
그리고 pb의 횟수, 스택 b에 쌓이는 숫자의 개수는 인자로 들어온 숫자들의 총 개수의 절반을 넘지 않도록 한다.

일단 기본적으로 지켜야 한다..?는 이정도를 생각해봤다. 그래서 일단은 위의 세 변수들을 저장하는 함수를 만들기로 했다.

max, min, mid 값 구하기

먼저 max 값을 구하는 함수를 만들었다. 첫 노드의 값 node->valuemax로 설정하고, 노드를 끝까지 넘기면서 max 보다 node->value가 크면 max를 현재 node->value로 바꿔주었다.

min 값을 구하는 함수도 똑같이 만들었다. 첫 노드의 값 node->valuemin으로 설정하고, 노드를 끝까지 넘기면서 min 보다 node->value가 작으면 min을 현재 node->value로 바꿔주었다.

문제는 mid이다. 이걸 어떻게 구해야 하는지 모르겠어서 검색해보니까 숫자가 세 개일 때가 대부분이고 그게 아니면 정렬을 한 후에 중간에 위치한 값을 가져오는 것만 나왔다.
근데 애초에 이 프로그램이 정렬하는 프로그램인데 그건 좀 아닌 것 같고.. 뭐 대충 버블정렬로 하기에도 인자가 몇 천 개, 만 개가 들어올 수도 있는데 그렇게 하는 것도 좀 그래서 그 방법은 포기했다.

그리고 생각한 방법이, 최소값과 최대값을 구했으니까 그 두 값을 더해서 2로 나눈 값을 하나 구한다. 이 값을 num이라고 하자.
그리고 numnode->value의 차이(양수)를 구한다.
그리고 다음 노드가 있는지 확인한 후에 다음 노드가 존재하면 다시 numnode->next->value의 차이(양수)를 구한다.
그리고 두 차이값 중 더 작은 값을 가진 노드가 temp가 된다. tempt_node 형 변수이다.
그렇게 노드를 끝까지 넘기면서 구하고 최종 temp->valuemid가 된다.

이렇게 코드를 작성해서 값을 구했는데, 결론을 실패~! 🤦🏻‍♀️

숫자들끼리의 차이가 극단적일 때가 문제였다.
예를 들어, 8 2 5 73 3 로 들어왔을 때 내가 기대하는 중간값은 5 인데 결과는 8 이 나온다.
99 100 1 2 110 98 97 이렇게 들어왔을 때는 98 이 나와야 하는데 97 이 나온다.
차이가 1밖에 안 돼서 괜찮지 않을까 싶기도 한데, 그건 아직 모르는 거니까...

(+ mid 값은 쓰지 않게 되어서 구하는 함수를 만들지 않았다.)


썼다가 지움

하핳
썼다가 지웠다.
왜냐? 아예 잘못된 그니까 알고리즘이 아니라 하튼 잘못되었기 때문.
다시 합니다. 광광우럭딱


마무리

아몰랑 마무리

집에 갈 것이다.

하던 방법이 너무 잘못된 걸 알아서 다시 처음부터 하기로 했다.
뭔가 너무 간단하게만 생각했던 것 같다. (>ㅅ<;)

profile
It's me, jkeum!

0개의 댓글