정렬되지 않은 정수 배열이 주어졌다고 가정해 보겠습니다. 이때 우리가 해야 할 일은 주어진 배열에 존재하지 않는, 즉 [0부터 n] 범위 안에서 빠져 있는 양의 정수를 찾아내는 것입니다.
예제
입력 1
N = 9 arr = [0,2,5,9,1,7,4,3,6]
출력
8
설명: 주어진 정렬되지 않은 배열에서 '8'만이 빠져 있는 양의 정수이므로 출력값은 '8'입니다.
입력 2
N = 1 arr = [0]
출력
1
설명: 주어진 배열에서 '1'만이 빠져 있는 양의 정수이므로 출력값은 '1'입니다.
문제 해결 접근 방법
이 문제를 푸는 방법은 여러 가지가 있지만, 선형 시간 O(n)과 상수 공간 O(1)만으로도 충분히 해결할 수 있습니다.
핵심 아이디어는 배열의 크기가 n이고 원소들이 정확히 [0부터 n] 범위에 속한다는 사실을 활용하는 것입니다. 각 배열 원소와 그 인덱스, 그리고 n에 대해 XOR 연산을 차례로 수행하면, 최종 결과값으로 배열에서 빠진 고유한 숫자 하나를 얻을 수 있습니다. 이것이 가능한 이유는 XOR 연산이 같은 값끼리 만나면 0이 되고, 한 번만 등장한 값은 그대로 남는 성질을 가지고 있기 때문입니다. 덕분에 중복되는 값들은 모두 소거되고 누락된 숫자만 남게 됩니다.
- 크기 N인 배열을 입력받습니다. 배열의 원소는 [0부터 n] 범위에 있습니다.
- 정수 함수 findMissingNumber(int arr[], int size)는 배열과 그 크기를 입력으로 받아 누락된 숫자를 반환합니다.
- 누락된 숫자를 담을 변수를 배열의 크기(n)로 초기화한 뒤, XOR 연산을 시작합니다.
- 배열의 모든 원소를 순회하면서 각 원소와 해당 인덱스를 누락된 숫자 변수에 대해 XOR 연산합니다.
- 순회가 끝나면 최종적으로 누락된 숫자를 반환합니다.
구현 예제
public class Solution {
public static int findMissingNumber(int arr[], int size){
int missing_no= size;
for(int i=0;i<size;i++){
missing_no^= i^arr[i];
}
return missing_no;
}
public static void main(String[] args){
int arr[] = {0,4,2,1,6,3};
int n = arr.length;
int a=findMissingNumber(arr, n);
System.out.println(a);
}
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
5
주어진 배열 {0,4,2,1,6,3}에는 '5'가 빠져 있으므로 프로그램은 5를 반환합니다. 이처럼 XOR 연산을 활용하면 추가적인 메모리 없이 단 한 번의 순회만으로 누락된 양수를 효율적으로 찾을 수 있습니다.