[알고리즘문제] 빠진 숫자 찾기 ..
글쓴이: Sailor_moon / 작성시간: 금, 2011/11/04 - 5:44오전
안녕하세요 ... 알고리즘 스터디 하던 도중 ... 여러분들의 의견을 들어보고 싶은것이
생겨서 질문 올려봅니다.
1 , 2 , .... N 까지의 숫자가 있다고 할때, (정렬되지 않았습니다. 예를들어 n = 5 , 3 4 1 2 5 ... )
숫자 하나가 빠져있습니다.
어떤 방법이 이 숫자 하나 빠진 것을 찾는 좋은 방법일까요 ?
바이너리 트리를 생성한 다음에 해볼까 했는데 ... 결국 n번만큼의 스캔은 피할수가 없더군요.
공간 복잡도보다 시간 복잡도만을 볼때요 ~
여러분의 좋은 의견 부탁드려요 !
Forums:
딱 1개만 빠져 있다면 1~N까지 N-1개의 수열을
딱 1개만 빠져 있다면
1~N까지 N-1개의 수열을 전부 더한 값을 N*(N-1)/2에서 빼주는게 가장 간단하겠네요.
피할 수 있을때 즐겨라! http://melotopia.net/b
수식이 틀렸네요
N*(N+1)/2겠죠? FYI.
이거 유명한 문제인데요전부 XOR 시키면 빠진
이거 유명한 문제인데요
전부 XOR 시키면 빠진 숫자가 나옵니다.
물론,
좀 더 assumption을 명확하게 기술하자면
#1. 1 - N까지의 integer가 있다.
#2. N - 1의 size를 갖는 array가 있다.
#3. array에 1 - N의 숫자들을 "하나씩" 넣었으나, 공간부족으로 한개는 빠졌다.
이 빠진 숫자를 찾아라
===========
정렬되지 않은 array에서 검색 대상의 충분한 힌트없이 검색을 하려면,
최소한 the size of array만큼 최소한 한번은 스캔을 해야합니다. 즉, O(N)보다 더 나은 검색이 나오기 힘듭니다.
이미 한번 스캔을 하면서 정렬시켜놓고 다시 검색을 한다면야...이미 "정렬되지 않은 array에서의 검색"이 아니겠죠.
참고로, 질문자분이 쓰신것처럼 스캔을 하면서 바이너리 트리로 재구성을 한다면
그것만으로도 이미 O(NlogN)입니다.
좋은 방법같기는 한데요...
이 방법은 N = 2^n - 1인 경우에만 되는 것 아닌가요?
begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}
네 맞습니다.
그걸 깜빡했네요.
N이 2의 제곱수 일때로 해도 됩니다. ( 1,2,4,8,16,32 )
(주어진 수들을 모두 xor한 결과) xor N
가령,
N이 4일때,
3 ^ 1 ^ 4 ^ 4 (마지막 4는 N으로써의 4) 결과는 2
1 ^ 2 ^ 3 ^ 4 (마지막 4는 N으로써의 4) 결과는 4
N(N+1)/2에서 다 더한수를 빼면 되지 않을까요.
N(N+1)/2에서 다 더한수를 빼면 되지 않을까요. 이걸 바꿔보면 x = N(N+1)/2 - Sum{x_i} 이고 모든 숫자가 N+1 보다 작으니까 mod N+1에서 계산하면 더 쉽겠네요. 시간은 O(N) 이하로 못줄이고요, 공간은 O(1)이면 될듯합니다.
N(N-1)/2에서 모두 더한 값을 빼는 것과 전부
N(N-1)/2에서 모두 더한 값을 빼는 것과 전부 XOR하는 것이 수학적으로는 동치네요.
O(N)보다 작게 만들기는 어려울 것 같습니다.
피할 수 있을때 즐겨라! http://melotopia.net/b