22.04.30. push_swap - 정렬 알고리즘 최적화-2

현재 300개 이상의 인풋이 들어올 경우, 5500개 이하의 명령어 사용을 위해 정렬 알고리즘을 최적화를 해야 한다. 현재 300개 이하의 인풋에서는 구간의 갯수가 60개일 때가 70개일 때 보다 사용하는 명령어의 갯수가 적음을 확인했고, 360개 이상의 경우에는 70개인 경우가 60개일 때보다 사용하는 명령어의 갯수가 적었다. 또, 500개의 경우엔 각 구간의 갯수가 70개일 때보다 100개일 경우가 명령어 사용량이 훨씬 적었다.

각 구간 70개, 인풋 300개 : 5316개

각 구간 60개, 인풋 5197개 : 5197개

이 결과를 미루어 볼때, 정렬시 구간이 5개 일때 명령어를 최소한으로 쓸 수 있다고 예측했고, 이를 통해 다음과 같이 각 구간의 크기를 변화시켜 output을 얻어보았다.

 

 

 

275개 인풋 : 4900개 => 구간당 60개

300개 인풋 : 5313 => 구간당 70개

360개 인풋 : 7746개 => 구간당 80개

420개 인풋 : 10502 => 구간당 90개

480개 인풋 : 13823개 => 구간당 90개

500개 인풋 : 14555개 =>구간당 100개

350개 인풋 : 7244 => 구간당 70

320개 인풋 : 6395 => 각 구간 70개

310개 인풋 : 5834개 => 구간당 70

각 구간을 최적화하기 위해 여러 테스트 케이스들을 만들었다.

300개 인풋 : 5193 => 구간당 60 (70일때 보다 good)

310개 인풋 : 6392 => 구간당 60 (70일때 보다 bad)

300개 까지만 구간 60으로 결정하고, 나머지 300이상의 값에 대한 최적화는 다른 방식으로 접근 해야 할 것 같다는 생각이 들었다.