알고리즘/ 빠진 양의 정수 찾기 _PHP

https://app.codility.com/demo/results/trainingB9KEUF-S3A/

전에 비슷한 문제를 풀어봤는데, 다시 푸니까 망 ㅇ0ㅇ

테스트를 다양하게 해봅시다.

function solution($A) { $result = 0; $N = sizeof($A); if ($N < 1 || $N > 100000) return $result; $max = 0; $tmp = array(); for ($i = 0 ; $i < $N ; $i++) { if ($A[$i] < -1000000 || $A[$i] > 1000000) return $result; if ($A[$i] > 0) { $max = $max < $A[$i] ? $A[$i] : $max; $tmp[$A[$i]] = 1; } } if ($max == 0 && sizeof($tmp) == 0) { $result = 1; return $result; } $cnt = 0; for ($i = 1 ; $i <= $max; $i++) { if (!isset($tmp[$i])) { $result = $i; $cnt++; } } if ($cnt == 0) { $max++; $result = $max; } else if ($cnt > 1) { $result = 0; } return $result; }

https://app.codility.com/demo/results/trainingWCEUZU-DS6/

이렇게 점수가 낮아지는건 또 처음

function solution($A) { $result = 0; $N = sizeof($A); if ($N < 1 || $N > 100000) return $result; $max = $min = 0; $tmp = array(); for ($i = 0 ; $i < $N ; $i++) { if ($A[$i] < -1000000 || $A[$i] > 1000000) return $result; if ($A[$i] > 0) { if ($i == 0) $max = $min = $A[$i]; $max = $max < $A[$i] ? $A[$i] : $max; $min = $min > $A[$i] ? $A[$i] : $min; $tmp[$A[$i]] = 1; } } if ($max == 0 && sizeof($tmp) == 0) { $result = 1; return $result; } $cnt = 0; for ($i = $min ; $i <= $max; $i++) { if (!isset($tmp[$i])) { $result = $i; $cnt++; } } if ($cnt == 0) { $max++; $result = $max; } else if ($cnt > 1) { $result = 0; } return $result; }

https://app.codility.com/demo/results/trainingZY88JN-AST/

퍼포먼스 점수 100 실화 입니까!? ㅠ-ㅠ

알고리즘 막막했는데 그래두 자꾸자꾸 하다보니까 가장 기본적으로

이중 for문 안 돌리려고 노력노려쿠 ㅠㅠ

근데 테스트 케이스에서 값이 잘못 나온 것은.. 나의 문제 이해도가 100%이지 못하단 증거되겠다 ㅇ-ㅇ;;

올 100을 향하여...

function solution($A) { $result = 0; $N = sizeof($A); if ($N < 1 || $N > 100000) return $result; //get max number -> counting the number $max = $min = 0; $arr_count = array(); for ($i = 0 ; $i < $N ; $i++) { if ($A[$i] < -1000000 || $A[$i] > 1000000) return $result; if ($A[$i] > -1) { $max = $max < $A[$i] ? $A[$i] : $max; if ($i == 0) $min = $A[$i]; else $min = $min > $A[$i] ? $A[$i] : $min; } } if ($max == 0) { // all elements are negative integers $result = 1; return $result; } if ($min <= 0) $min = 0; for ($k = 0 ; $k < $N ; $k++) { if ($A[$k] > -1) { if (!isset($arr_count[$A[$k]])) $arr_count[$A[$k]] = 1; else $arr_count[$A[$k]]++; } } $size = sizeof($arr_count); $d = $max - $min; if ($d >= $size) { ksort($arr_count); $_tmp = $min+1; foreach ($arr_count as $key=>$val) { $_tmp = $_tmp != $key ? $_tmp : $_tmp+1; } $result = $_tmp; } else if ($d > 0 && ($size-$d) == 1) { $result = $min > 1 ? 1 : ($max+1); } else { $result = $min > 1 ? 1 : ($min > 0 ? 2 : 1); } return $result; }

https://app.codility.com/demo/results/trainingRP9YHY-BDG/

집념이 통했다!!!! 여러 문제를 풀 때마다 느끼는 거지만... 테스트 케이스에 따라 예상 값도 잘 예측해야해. ㅠㅠ

문제에 나온 테스트 케이스만 가지고 생각해서는 안되구 말로 설명된 것을 잘 이해해야 한다 ㅠㅠ

한 때는 이 문제를 풀면서 max 값까지 인덱스를 가지는 배열을 만들어서

각 숫자마다 카운트 하려고 했는데, 연속된 숫자라는 조건이 있다면 그 방법이 통할지 모르겠지만

이 문제에는 '연속'된 숫자라는 조건은 없다. 그래서 그냥 숫자를 키로 하는 배열만 만들고

foreach 로 돌린게 포인트!!! 그냥 무작정 max크기의 배열을 만들어 돌렸다면

[3, 10, 95] 처럼 숫자 간 간격이 클 경우 불필요한 부하가 발생하겠다 ㅇ-ㅇ

function solution($A) { $result = 0; $N = sizeof($A); if ($N < 1 || $N > 100000) return $result; //get max number -> counting the number $max = $min = 0; $arr_count = array(); for ($i = 0 ; $i < $N ; $i++) { if ($A[$i] < -1000000 || $A[$i] > 1000000) return $result; if ($A[$i] > -1) { $max = $max < $A[$i] ? $A[$i] : $max; if ($i == 0) $min = $A[$i]; else $min = $min > $A[$i] ? $A[$i] : $min; } } if ($max == 0) { // all elements are negative integers $result = 1; return $result; } for ($k = 0 ; $k < $N ; $k++) { if ($A[$k] > -1) { if (!isset($arr_count[$A[$k]])) $arr_count[$A[$k]] = 1; else $arr_count[$A[$k]]++; } } $size = sizeof($arr_count); $d = $max - $min; if ($d >= $size) { ksort($arr_count); $_tmp = $min > 1 ? 1 : $min+1; foreach ($arr_count as $key=>$val) { $_tmp = $_tmp != $key ? $_tmp : $_tmp+1; } $result = $_tmp; } else if ($d > 0 && ($size-$d) == 1) { $result = $min > 1 ? 1 : ($max+1); } else { $result = $min > 1 ? 1 : ($min > 0 ? 2 : 1); } return $result; }