136. Single Number

개요

문제 해결 강의에서 leetcode의 Single Number와 비슷한 문제 해결 고민을 한 내용을 정리해 보았다.
이후에 Single Number 문제를 해결한 코드를 제시하겠다.

문제 내용 요약은 아래와 같다.

자연수가 여러 개 제시된다. 이때 하나의 수만 한 개만 제시되고, 나머지 수들은 두 개씩 제시된다. 한 개만 제시된 수를 구하라.

---

A안) 한 인덱스의 짝 존재 여부 확인

(정렬없이) 인덱스 0의 짝 존재 여부 확인 -> 인덱스 1의... -> 인덱스 2의... -> 인덱스 n-1의... 를 순서대로 확인하는 방법이다.

이때, 확인된 짝의 인덱스를 범위 밖의 값으로 변경하거나 linked list 자료형을 이용해 아예 값을 제공하는 방법으로 약간 시간을 줄일 수 있을 것 같다.

시간 복잡도는 O($n^2$)이다.

---

B안) check 배열 이용

check 배열을 따로 두고 해당 배열의 인덱스를 제공되는 수로 생각하여, 수가 확인되면 값을 1로 다시 확인되면 0으로 바꾸는 방법이다.

결론적으로 check 배열에서 홀로 값이 1인 인덱스 값이 답이 된다.

시간 복잡도는 O($n$)이다.

다만, 입력 범위가 작을 때 유효한 방법이고, 입력 값의 범위가 크다면 메모리 초과 위험이 발생한다.

---

C안) 정렬 이후 확인

O($n logn$) 시간 복잡도의 정렬 알고리즘을 사용해 정렬하고, 연속된 두 수가 짝을 이루는 지 확인하는 방법이다.

시간 복잡도는 O($nlogn$)이다.

---

D안) Hashing

Hashing을 이용하는 방법이다. Hash 함수를 잘 구현한다면 시간복잡도를 O($n$)으로 낮출 수 있으며, check 배열을 사용하는 B안에 비해서 메모리 사용을 줄일 수 있다.

다만, 구현 방법이 굉장히 까다로울 것이다.

---

E안) 비트 연산 이용

비트 연산 중에서 ^(Xor)를 이용하는 방법이다. 같은 두 수를 ^(Xor)하면 0이 되고, 결합 법칙(세 수 이상의 연산에서 순서를 바꿔도 결과가 동일)이 성립한다.

따라서 제시된 모든 수를 ^(Xor)하고 난 뒤 남은 수는 한 개만 제시된 수이다.

---

Single Number 문제 해결 코드

🔗https://leetcode.com/problems/single-number/

int singleNumber(int* nums, int numsSize) {
    /* using check array */
    char pos[300001] = {0};
    char neg[300001] = {0};

    for (int i = 0; i < numsSize; i++) {
        if (nums[i] >= 0)
            pos[nums[i]] = pos[nums[i]] == 0? 1 : 0; // toggle
        else
            neg[-nums[i]] = neg[-nums[i]] == 0? 1 : 0; // toggle
    }

    for (int i = 0; i < 300001; i++) {
        if (pos[i] == 1)
            return i;

        if (neg[i] == 1)
            return -i;
    }

    return 0;
}

위의 코드는 leetcode의 Single Number 문제의 경우, 입력 범위가 작기 때문에 간단한 B안을 이용해서 해결한 것이다.

반면, 아래 코드는 비트 연산자를 이용해 해결해 보았다.

int singleNumber(int* nums, int numsSize) {
    /* using bitwise operator */
    int target = nums[0];
    for (int i = 1; i < numsSize; i++)
        target ^= nums[i];

    return target;
}

실행 시간의 경우, check 배열을 이용하는 코드가 13ms, 비트 연산을 이용하는 코드가 11ms가 나온다.