[push_swap] 5. 최적화

알고리즘 구현을 완료하고 Push_swap Visualizer를 이용하여 정렬 과정을 시각화 해보면 알고리즘에서 불필요하게 스택이 회전하는 과정을 발견할 수 있다.

https://github.com/o-reo/push_swap_visualizer

GitHub - o-reo/push_swap_visualizer: This python script was created to visualize your work with the PUSH_SWAP 42 Project.

(주의 : MacOS 12이상에서는 제대로 안돌아가는 듯 하다...)

 

내가 최적화해준 부분은 크게 2가지였다.

 

1. 첫 번째 a_to_b가 끝나기 전까지는 rra를 해줄 필요가 없음

a_to_b와 b_to_a를 반복하며 정렬을 하는 과정 중 a스택에서 피봇보다 큰 값을 ra로 넘겨주는 과정을 거치고, 정렬된 상태를 유지하기 위해 a_to_b의 마지막에 rra로 ra를 한 만큼 스택을 다시 돌려주게 된다.

그러나 최초로 a스택에서 b스택으로 원소를 넘겨줄 때에는 이 rra가 의미 없는 연산이 된다. 어차피 b스택으로 다 넘길건데 정렬된 상태를 유지할 필요가 없기 때문...

따라서 b_to_a 가 실행되기 전에는 rra가 실행되지 않도록 최적화를 해주었다.

 

2. 정렬해야하는 숫자의 갯수가 3개, 5개일 때 최적화

내가 사용한 알고리즘은 정렬해야 하는 숫자의 갯수가 적을 때 필요 이상으로 연산이 진행된다는 문제가 있었다.

그런데 재귀 알고리즘이 진행될 수록 정렬해야하는 숫자의 갯수가 점점 적어지는데, 결국 마지막에는 5개 이하의 숫자를 정렬하는 알고리즘이 반복되게 된다. 

따라서 5개 이하의 숫자를 정렬하는 알고리즘을 별도로 작성하여 최적화 해주었다.

 

이 외에도 평가를 진행하며 몇 가지 아이디어를 더 얻을 수 있었는데,

 

3. r과 rr압축

연산의 목록을 주욱 보면 정렬이 끝난 후 스택을 rr해주고 다음번 재귀에서 다시 피봇보다 크거나 작은 숫자를 찾기 위해 r로 스택을 돌리는 연산이 반복되는 경우가 많다. 이때 굳이 스택을 다 감아버릴 필요 없이 피봇보다 크거나 작은 숫자의 위치까지만 스택을 감아주도록 최적화 할 수 있음.

 

4. rra와 rrb, ra와 rb압축

이 두 명령어는 각각 rrr과 rr로 압축할 수 있다.