-
[풀이]
Let a, i=1,n be the original numbers, Let b,i=1,n-2 be the given numbers (i.e. original numbers except two missing numbers).
An = a[1] + a[2] + … + a[n]
Bn = a[1]^2 + a[2]^2 + … + a[n]^2Cn = b[1] + b[2] + … + b[n-2]
Dn = b[1]^2 + b[2]^2 + … + b[n-2]^2Note we can find the smallest number and biggest number from the given numbers b[j], j=1,n-2 in O(n).
Let x,y be the missing numbers.
x+y = An – Cn
x^2 + y^2 = Bn – DnSolve the systems of equation.
Computing time 은 가장 작은수와 가장 큰수를 찾기위해 O(n) 이 필요하고, 필요한 Storage 는 계산에 필요한 약간의 메모리정도.
씨애틀님 방법도 가능하지만, 주어진 숫자가 많아지면 (즉, n 값이 커지면) 전체곱한 값이 너무 커져서 Overflow가 나겠네요.
이상입니다.
>퍼즐이라기 보다는 알고리즘문제라고 할 수도 있겠네요.
>
>n-2 개의 숫자가 Array나 List에 저장되어 있습니다. 원래는 n개의 일련숫자(이를테면 6,7,8,9,..,6+(n-1)) 였는데, 가장 작은 수와 가장 큰 수를 제외하고 숫자 두개를 삭제한 후에 순서를 랜덤하게로 재 배열한 것입니다. (즉, Sorting이 되어있지 않습니다.)
>
>문제는 제거된 두 숫자를 찾아내는 것인데, 조건은 계산에 필요한 storage에 제약이 있습니다. 즉, O(N)보다 작다는 것입니다. (참고로 O(n)개의 storage 가 주어진다면 너무나 쉬운 문제가 되겠지요?) 그리고 Computing Time은 O(n)입니다.
>
>예를 들어서 12,7,9,5,4,10,11 이 주어진다면, 없어진 두 숫자는 6과 8이 되겠네요. (하루나 이틀후에 답이 없으면, 답을 올리겠습니다. 정답이 반드시 하나일 필요는 없겠지요.)
>
>[제안] 아래 어느분께서 IT 인터뷰 족보 자료를 정리하고 계신데, 무척 좋은 일이라고 생각합니다. 이곳 싸이트에 그런 용도로 게시판을 하나 만들었으면 좋을 것 같네요. 질문도 하고 답도 올리고 의견도 교환하고… 혹시 이런 싸이트가 이미 있다면 알려주세요.