알고리즘/ 배열에서 짝없는 원소 찾기 _PHP

https://app.codility.com/demo/results/training27P63H-25J/

하하... 이미 풀 때부터 너무 조건문이 많아서 이건 아니다 싶었어.

정말 아니구나 ;) 밤이 깊었으니 내일이나 나중에 다시 풀어봐야할듯 ㅠ_ㅠ

function solution($A) { $rs = 0; $tmp = array(); $idx = $max = 0; for ($i = 0 ; $i < sizeof($A) ; $i++) { if ($i > 1) { if ($A[$i-2] == $A[$i]) { if ($tmp[$max][0] == $A[$i]) { if ($tmp[$max][1] < 1) $tmp[$max][1]++; else { $max++; $tmp[$max] = array($A[$i], 0); } } else if ($tmp[$max-1][0] == $A[$i]) { if ($tmp[$max-1][1] < 1) $tmp[$max-1][1]++; else { $max++; $tmp[$max] = array($A[$i], 0); } } else { $max++; $tmp[$max] = array($A[$i], 0); } } else { $max++; $tmp[$max] = array($A[$i], 0); } } else { $max = $idx+$i; $tmp[$max] = array($A[$i], 0); } } for ($i = 0 ; $i < sizeof($tmp) ; $i++) { if ($tmp[$i][1] == 0) $rs = $tmp[$i][0]; } return $rs; }

https://app.codility.com/demo/results/trainingHWZVG6-E6Z/

55점까지 끌어올리긴 했지만... 배열 크기가 커지면 시간 엄청 잡아먹는 로직...

어쩐지 평가하는데 뱅글뱅글 오래 돌더라 ㅠ.ㅠ

function solution($A) { $result = 0; $N = sizeof($A); if ($N > 1000000) return $result; for ($i = 0 ; $i < $N ; $i++) { for ($j = $N-1 ; $j > $i ; $j--) { if ($A[$i] == $A[$j]) { $A[$i] = null; $A[$j] = null; } } } $A = array_filter($A); if (sizeof($A) == 1) { foreach($A as $a) $result = $a; } return $result; }

https://app.codility.com/demo/results/trainingC8QYST-J42/

조건 비교해도 소용없는 건 건너뛰도록 하니까 초큼 더 퍼포먼스 점수가 올라가긴 했다.

근데 여전히 시간 복합도 O(N**2) 어쩔...

모든 원소를 확인해야하니까 for 문을 아예 안 돌릴수는 없는데 ㅠㅠ

음.. 같으면 값을 지워버리는데. 같지 않는 경우에 무슨 플래그라도 줘볼까?

같지 않은 경우, 새로운 배열에 두 값의 위치를 저장하고 -> 같은 값 찾으면 새로운 배열에 등록된 위치인지 찾아서 같이 지워보면?

결국 그게 그거... 괜한 거 추가되는거 같기도 ㅇ-ㅇ

function solution($A) { $result = 0; $N = sizeof($A); if ($N > 1000000) return $result; for ($i = 0 ; $i < $N ; $i++) { if ($A[$i] != null && $N > 0) { for ($j = $N-1 ; $j > $i ; $j--) { if ($A[$j] != null && $A[$i] == $A[$j]) { $A[$i] = null; $A[$j] = null; break; } } } } $A = array_filter($A); if (sizeof($A) == 1) { foreach($A as $a) $result = $a; } return $result; }

https://app.codility.com/demo/results/trainingFXJNUX-GKY/

고민고민 하니까 되었다규 100점 됐다규 ;)

툭하면 반복문을 애용했던 내 코딩 습관?을 고칠 수 있는 시간이 된 것 같다 :0)

function solution($A) { $result = 0; $N = sizeof($A); if ($N > 1000000) return $result; $tmp = array(); for ($i = 0 ; $i < $N ; $i++) { if(!isset($tmp[$A[$i]])) $tmp[$A[$i]] = 0; $tmp[$A[$i]] += 1; } $cnt = 0; foreach ($tmp as $k=>$v) { if ($v % 2 != 0) { $result = $k; $cnt++; } } if ($cnt > 1) $result = 0; return $result; }