프로그래밍 면접 문제 4 : Find Missing Element
프로그래밍 면접 문제 4 : Find Missing Element
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 질문 3 : Largest Continuous Sum
음수가 아닌 정수로 채워진 배열이 있습니다. 첫 번째 배열 요소들을 이동시키고, 랜덤으로 특정 요소를 하나 삭제한 다음 두 번째 배열을 만듭니다. 이렇게 두 배열이 주어지면, 두 번째 배열에서 누락된 요소를 찾습니다. 다음은 입력 값의 예로, 첫 번째 배열에서 각 배열요소를 이동시키고, 숫자 5를 배열에서 삭제한 다음 두 번째 배열을 생성했습니다.
순진한 방법으로 접근해보면, 배열을 순회하면서 첫 번째 배열의 요소가 두 번째 배열에 존재하는지 확인하는 방법이 있습니다. 여기에서 주의할 점은, 배열의 요소 중에 중첩된(두 개 이상 존재하는)요소가 있을 수 있다는 점입니다. 이 접근 방법의 복잡도는 O(N^2)입니다. 이 방법보다 좀 더 효율적인 해결 방법은 첫 번째 배열을 정렬한 다음, 두 번째 배열 요소와 비교하는 것으로, 이진 검색(Binary Search)을 이용할 수 있습니다. 하지만 여전히 중첩된 배열 요소에 대해서는 주의를 해야합니다. 이 방법의 복잡도는 O(NlogN)입니다. 배열 요소가 중첩된 특별한 경우를 고려하지 않는다면, 두 배열을 모두 정렬하고 동시에 비교해볼 수 있습니다. 배열을 순회하다가 두 배열이 각각 가리키는 요소의 값이 다르면 그 위치에서 멈춥니다. 이 위치의 첫 번째 배열의 요소가 누락된 요소입니다. 이 해결책의 복잡도는 O(NlogN)입니다. 다음은 이 접근 방법에 대한 알고리즘 풀이 입니다(C#):
int FindMissingNumber1(int[] array1, int[] array2)
{
Array.Sort(array1);
Array.Sort(array2);
for (int ix = 0; ix < array2.Length; ++ix)
{
if (array1[ix] != array2[ix])
return array1[ix];
}
return -1;
}
좀 더 효율적으로 해결할 수 있는지 살펴보겠습니다. 대부분의 면접에서 선형 시간 복잡도를 갖는 해결책을 요구합니다. 이를 위해서, 해시테이블에 두 번째 배열의 각 배열 요소가 나타나는 횟수를 저장합니다. 그 다음, 첫 번째 배열의 각 요소를 순회하면서 해시테이블에 저장된 횟수를 하나씩 감소시킵니다. 해시테이블에서 횟수가 0인 요소가 누락된 요소입니다. 다음은 이 접근 방법에 대한 알고리즘 풀이 입니다(C#):
int FindMissingNumber2(int[] array1, int[] array2)
{
Dictionary<int, int> dictionary = new Dictionary<int, int>();
for (int ix = 0; ix < array2.Length;++ix)
{
if (dictionary.ContainsKey(array2[ix]))
dictionary[array2[ix]] += 1;
else
dictionary.Add(array2[ix], 1);
}
for (int ix = 0; ix < array1.Length;++ix)
{
if (!dictionary.ContainsKey(array1[ix]))
return array1[ix];
}
return -1;
}
이 방법의 시간 복잡도는 O(N)이지만 해시테이블을 사용했기 때문에 공간 복잡도는 역시 O(N)입니다. 일정한 공간 복잡도를 갖는 해결책이 가장 이상적일 것입니다. 한 가지 가능한 접근 방법은 첫 번째 배열과 두 번째 배열의 요소를 모두 각각 더한 다음, 첫 번째 배열 요소를 모두 더한 값에서 두 번째 배열 요소를 모두 더한 값을 빼는 방법입니다. 이 계산의 결과가 두 번째 배열에서 누락된 요소입니다. 하지만 이 방법은 다소 문제가 있습니다. 배열의 크기가 매우 크거나 배열 요소가 너무 큰 경우에는, 각 수를 더하면서 오버플로우(Overflow)가 발생할 수 있습니다.
아주 영리한 방법을 이용하면, 이러한 문제 없이 선형적인 시간 복잡도와 일정한 공간 복잡도를 갖는 해결책을 찾을 수 있습니다. 그 방법은 이렇습니다: 변수를 하나 선언한 다음 0으로 초기화하고, 첫 번째와 두 번째 배열의 모든 요소를 해당 변수로 XOR합니다. 계산이 종료된 후, 변수에 저장된 값이 두 번째 배열에서 누락된 요소입니다. 괜찮은 방법이지 않습니까? 다음은 이 방법에 대한 코드 입니다(C#):
int FindMissingNumber3(int[] array1, int[] array2)
{
int result = 0;
int[] array3 = new int[array1.Length + array2.Length];
Array.Copy(array1, array3, array1.Length);
Array.Copy(array2, 0, array3, array1.Length, array2.Length);
for (int ix = 0; ix < array3.Length; ++ix)
{
result ^= array3[ix];
}
return result;
}
이 접근 방법이 왜 동작하는지 분석해보겠습니다. 두 수를 서로 XOR하면 어떤 일이 발생할까요? 여기서 우리는 십진수 단위 대신 비트 단위로 생각해야합니다. 4 비트 숫자를 1011로 XOR하면, 그 숫자의 첫 번째, 세 번째, 네 번째 비트가 뒤집힙니다. 이렇게 나온 결과를 1011로 다시 XOR하면 뒤집혔던 비트들이 재차 뒤집혀서 원래의 값이 됩니다. 즉, 어떤 숫자를 특정 숫자로 두번 XOR 처리하면 변화가 없습니다. 여러 개의 숫자를 XOR할 수 있고, 그 순서는 상관이 없습니다. 예를 들어, 숫자 n1과 n2를 XOR하고 그 결과를 n3로 XOR합니다. 그리고 이 결과를 n2로 XOR하고 다시 n3로 XOR합니다. 이렇게 하면 최종적으로 계산된 결과는 숫자 n1이 됩니다. XOR 연산은 특정 비트를 뒤집는데, 같은 숫자로 다시 XOR 연산을 하게되면 재차 그 비트들이 다시 뒤집히기 때문입니다. 따라서, XOR 연산의 순서는 중요하지 않습니다. 특정 숫자로 XOR 연산을 짝수번 하게되면 결과에 아무런 영향을 미치지 않습니다.
위의 코드에서 첫 번째 배열과 두 번째 배열의 모든 숫자를 XOR했습니다. 두 번째 배열의 모든 요소는 첫 번째 배열에 나타나지만, 첫 번째 배열에는 두 번째 배열에서 누락된 숫자가 하나 더 존재합니다. 따라서 두 번째 배열 요소의 각 XOR 연산 효과는 첫 번째 배열의 동일한 요소와 XOR 연산이 되기 때문에 XOR 연산 효과가 사라집니다(XOR 연산의 순서는 중요하지 않다는 점을 명심합니다). 하지만, 첫 번째 배열에만 존재하는 숫자는 두 번째 배열에서 누락되었기 때문에 XOR 연산의 효과가 사라지지 않습니다. 따라서 모든 연산의 결과는 0과 두 번째 배열에서 누락된 숫자를 XOR한 것과 같은 결과가 됩니다. 숫자 0과 어떤 숫자를 XOR한 결과는 결국 그 숫자가 됩니다. 따라서, 모든 연산이 종료되면 두 번째 배열에서 누락되었던 숫자를 얻게 됩니다. 이 해결 방법의 공간 복잡도는 변수 하나를 추가로 사용하기 때문에 O(1)입니다. 시간 복잡도는 배열을 한번 순회하기 때문에 O(N)입니다.
이 문제는 비트 단위 연산의 강력함을 시험해볼 수 있고, 효율적인 해결 방법을 얻기 위해서 비트 단위 연산을 사용하는 방법을 보여줍니다. 그래서 제가 가장 좋아하는 면접 문제 중 하나입니다.
