문제 #

const array = [1,0,3,4];

• 위 배열은 길이가 4입니다.

• 예로 배열에 순서대로 값을 채워넣는 경우 [0, 1, 2, 3]으로 이 때 빠진 값은 4입니다.

  • 0을 포함하기 때문에 배열의 길이와 빠진 수 없이 온전한 수열은 양립 할 수 없습니다.

• 위 배열에서 빠진 숫자는 2입니다.

해당 숫자를 O(n)의 시간복잡도와 O(1)의 공간복잡도를 사용해 빠진 숫자 2를 찾아봅시다.

bitwise operator - xor를 사용하는 방법 #

xor는 두개의 비트에 대해 서로 다를 경우 1, 같을 경우 0을 반환합니다.

1 ^ 0 = 1 // = 01 ^ 00 = 01
2 ^ 1 = 3 // = 10 ^ 01 = 11

xor는 결합법칙과 교환법칙이 성립합니다.

let x = 0;
let y = 1;

x ^ y = y ^ x; // 00 ^ 01 == 01 ^ 00
x ^ (x ^ y) = y ^ (x ^ x) // 01 ^ (00 ^ 00)

문제의 조금 더 디테일한 이해 #

문제는 한 숫자 배열을 입력으로 줍니다. 예를 들어 [1, 0, 3, 4]를 배열로 주었을 때, 배열의 길이는 4입니다. 0 ~ 3까지의 배열을 순회하면서 총 가질 수 있는 숫자는 4개이므로 위 주어진 배열과 같이 2라는 값이 빠지게 됩니다. 이 때, 2를 반환하면 됩니다.

다시 예를 들면 [1, 2, 3]이라는 배열은 배열의 길이가 3이고 0이라는 값이 빠졌으므로 0을 반환하면 됩니다.

배열의 길이와 같은 메모리를 사용해 체크하면 O(n)만큼의 시간, 공간 복잡도를 사용해 문제를 해결 할 수 있겠으나, O(n)의 시간복잡도와, O(1)의 공간복잡도를 사용해 문제를 해결해야 합니다.

계산된 값으로 보는게 아닌 변수의 전달 측면으로 본다면.. #

const array = [1, 0, 3, 4];

function findMissingNumberFrom(array) {
    let xor = array.length;
    for(let i = 0; i < array.length; i++) {
        xor = xor ^ i ^ array[i];
    }
    return xor;
}

위 함수를 통해 이루어지는 반복문 안의 계산들을 나열해보겠습니다.

• 5 = 4 ^ 0 ^ 1
• 4 = 5 ^ 1 ^ 0
• 5 = 4 ^ 2 ^ 3
• 2 = 5 ^ 3 ^ 4 찾는 값 2

xor는 이전 값들의 결과를 계속 저장하는 역할을 합니다. 따라서 아래와 같이 나열해 볼 수 있습니다.

• 5 = 4 ^ 0 ^ 1에서 4 ^ 0 ^ 1을 계산한 결과가 5입니다.
• 따라서 4 ^ 0 ^ 1을 가져옵니다.
• 4 = 5 ^ 1 ^ 0에서 5는 이전 결과값이므로 ^ 1 ^ 0을 가져옵니다.
• 이 과정을 반복하면
• xor = 4 ^ 0 ^ 1 ^ 1 ^ 0 ^ 2 ^ 3 ^ 3 ^ 4이 됩니다.
• 이를 계산해보면 2라는 값이 도출됩니다.
• 즉 xor를 초기화한 것은 이전 xor의 계산 결과를 다음 반복문에 넘겨주는 역할을 합니다.

이제 xor의 값 자체에 주목하는 것이 아닌 xor는 이전에 무슨 값이였고, 값을 다음 반복문에 넘겨주는 역할도 한다는 것을 알게 되었습니다.

위와 같은 xor 연산도 좋습니다만 다른 방법도 있습니다. 예를 들어 배열의 총 합을 구합니다. 배열은 0부터 n까지 정렬되어 있지 않은 수의 집합이고 그 중 하나의 수만 빠져 있습니다. 따라서 0부터 n까지의 합을 구하고 실제 반복문을 돌아 총 합에서 반복문을 돌아서 구한 합을 빼주면 나오는 차의 값이 배열에서 누락된 값입니다.

재미있는 xor을 활용한 변수 swap #

위 문제는 변수를 다음 반복문으로 넘기는 방법을 사용했습니다.

위와 관련해 하나 더 재미있는 xor operator를 이용해 변수간 값의 swap이 가능합니다.

let a = 1;
let b = 2;

a = a ^ b;
b = a ^ b; // b ^ (a ^ b) == b ^ (b ^ a) == a 이제, b == a
a = a ^ b; // a ^ b ^ a == a ^ a ^ b == 0 ^ b == b 이제, a == b

a // 2
b // 1

놀랍게도 스왑이 이루어졌습니다.

bitwise operator의 숨은 장점은 잘 사용하는 경우 코딩을 정말 잘해보이는 효과가 있습니다. 🤣