[push_swap] Day 09. 최적화

jongeun·2021년 6월 5일
2

push-swap

목록 보기
9/10

최적화

하도 오랜만에 써서 뭐 쓰려고 했는지 까먹을 뻔했다. (까먹었다가 겨우 생각해냈다.)

100개일 때만 4점이 나와서 5점으로 채우기 위해 최적화를 했다.

방법 1

처음 생각했던 것은, b_to_a()에 들어가기 전까지 a_to_b()만 반복할 때는 rrrrra가 의미없이 돌아간다는 것이다.
그걸 해줘도 스택 a는 하기 전과 똑같기 때문에, rrb만 해주면 된다.

이것만 처리해도 확 줄일 수 있을 거라고 생각했다.

b_to_a()에 한 번도 안 들어갔을 때만 rrrrra를 안 하면 되는 거니까, b_to_a()에 한 번이라도 들어갔는지를 확인하는 변수를 만들었다.
intcnt 변수를 선언하고 0으로 초기화했다.
그리고 처음 push_swap()에서 a_to_b()를 호출할 때 &cnt로 넣어줬다.
b_to_a()에서도 주소값을 보내서 다른 함수에서 바뀐 값을 그대로 가지고 다니게 했다.

a_to_b()에서는 cnt의 값을 변경하지 않고, b_to_a()에 들어가면 기장 먼저 cnt 값을 +1 해준다.
이렇게 하면 한 번이라도 b_to_a()에 들어갔으면 cnt는 0이 아닌 값을 가지게 될 것이다.
이제 a_to_b()에서 rrrrra를 할 때, cnt 값이 0보다 큰지를 확인해서 0보다 클 때만 rrrrra를 해준다. 0보다 크지 않을 때는 rrb만 해준다.

방법 2

사실 이걸 먼저 했다.

hyunlee님이 알려주셔서 했다. Thanks~!

처음부터 인자가 5개만 들어왔을 때 말고, 함수를 막 호출하다가 정렬해야 하는 노드가 5개일 때를 처리했다.

스택 a에서는 5개 중에 중간값을 기준으로 중간값보다 작은 값들은 pb 했다.
그러면 이제 3개가 남는데, 이건 이전에 노드 3개를 정렬하는 함수를 그대로 사용했다.
스택 b로 보낸 노드 2개도 정렬해서 pa 해줬다.

스택 b에서는 스택 a와 반대로 정렬해야 하니까 5개 중에 중간값을 기준으로 중간값보다 크거나 같은 값들을 pa 했다.
그러면 이제 스택 a에 보낸 값 3개를 정렬한다.
그리고 스택 b에 남아있는 노드 2개도 정렬해서 pa 해줬다.

방법 1만 해도 확~! 줄긴 하는데, 이것까지 해줘야 100개를 정렬할 때 안정적으로 660개 내외로 나왔던 것 같다.


마무리

7일 만에 쓰다니 미쳤나

이제 체커만 만들면 된다.
Day 10 안으로 끝내는 게 큰 목표고 안 되면 Day 15 안에라도 끝내고 싶었는데 가능할 것 같다.
사실 Day 10이라고 진짜 공부한 날이 10일밖에 안 되는 건 아니구,,
내일 끝낸다고 쳤을 때 따지고 보면 2주 정도 한 것 같다.
어쨌든 나쁘지 않음~

profile
It's me, jkeum!

0개의 댓글