알고리즘/ 가장 짧은 거리 구하기 _PHP

https://app.codility.com/demo/results/trainingPJ93XE-8ZM/

조건은 충족했지만, 배열의 크기가 커질 수록 퍼포먼스는 현저히 떨어지는 로직 ㅇ_ㅇ

어렵.. ㅇ-ㅇ

function solution($A) { $result = 0; if (sizeof($A) < 2 || sizeof($A) > 100000) return $result; $tmp = 0; for ($p = 1 ; $p < sizeof($A) ; $p++) { $sum_a = $sum_b = 0; if ($A[$p] < -1000 || $A[$p] > 1000) return $result; for ($i = 0 ; $i < $p ; $i++) { $sum_a += $A[$i]; } for ($j = $p ; $j < sizeof($A) ; $j++) { $sum_b += $A[$j]; } if ($p == 1) $tmp = abs($sum_a - $sum_b); else $tmp = $tmp > abs($sum_a - $sum_b) ? abs($sum_a - $sum_b) : $tmp; } if ($tmp != null) $result = $tmp; return $result; }

https://app.codility.com/demo/results/trainingVQDJWB-BHU/

헤헷.. 생각해보면 굳이 저렇게 반복반복할 필요가 없는 거였다.

알고리즘 테스트 계속 해보면 생각하는 방향이 많이 달라질 거 같아.

function solution($A) { $result = 0; if (sizeof($A) < 2 || sizeof($A) > 100000) return $result; $arr_sum = array(); $sum = 0; for ($p = 1 ; $p < sizeof($A) ; $p++) { if ($A[0] < -1000 || $A[0] > 1000 || $A[$p] < -1000 || $A[$p] > 1000) return $result; $sum += $A[$p-1]; $arr_sum[] = $sum; if ($p == sizeof($A)-1) $sum += $A[$p]; } $tmp = 0; for ($i = 0 ; $i < sizeof($arr_sum) ; $i++) { if ($i == 0) $tmp = abs($arr_sum[$i]- ($sum-$arr_sum[$i])); else $tmp = $tmp > abs($arr_sum[$i]- ($sum-$arr_sum[$i])) ? abs($arr_sum[$i]- ($sum-$arr_sum[$i])) : $tmp; } $result = $tmp; return $result; }