#001 : Single Number

LeetCode Note #001

---

어렵지만 도전해볼 만한 문제가 있어 올려봅니다.
LeetCode의 136번 문제 "Single Number"입니다.

• https://leetcode.com/problems/single-number/description/

[ Description ]

int 자료형들의 배열이 주어지고, 단 하나의 원소를 제외한 나머지들은 두 번씩 나타납니다(중복된다는 뜻).

[ NOTE ]
알고리듬은 선형복잡도를 가져야합니다.
메모리를 추가로 사용하지않을 수 있습니까 ?

예시로, { 1, 3, 1, -1, 3 }이 입력되면 -1을 반환하면 됩니다.
보기에는 단순한 것 같지만, 알고 보면 쉽지않은 문제입니다.

아래는 Solution에 대한 설명이므로, 지금 보고 싶지않다면 내리지말아주세요.

[ Solution ]

방법 #1 - List operation [Time Limit Exceeded]

배열을 만들어, 그 배열에 원소를 집어넣고 삭제하는 연산을 반복합니다

알고리듬

1. 입력 vector의 모든 원소에 대해 반복합니다.
2. 지금 원소가 중복되는 것이 아닐 경우, 추가합니다.
3. 지금 원소가 중복되는 경우, 삭제합니다.

복잡도 분석

• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(n)
  → 결국, "시간제한 초과(Time Limit Exceeded)"로 이어집니다.

C++ 구현

int singleNumber(vector<int>& nums)
    {
        // 정답
        vector<int> result;
        // 중복여부
        bool bDup;
        // 중복된 곳
        int dupIndex;
        for (auto i : nums)
        {
            // 중복여부를 매번 초기화
            bDup = false;
            // 중복되는지 검사하고, 그럴 경우 그 위치와 중복여부를 저장
            for (int j = 0; j < result.size(); ++j)
            {
                if (result[j] == i)
                {
                    dupIndex = j;
                    bDup = true;
                }
            }
            // 중복될 경우, 정답에서 제외하고 그렇지않을 경우 정답에 추가
            if (bDup)
            {
                result.erase(result.begin() + dupIndex);
            }
            else
            {
                result.push_back(i);
            }
        }
        // 중복된 값이 모두 제거되고 나면, 단 하나의 값만 남게되므로
        return result.back();
    }

---

방법 #2 - Hash Table [Accepted]

원소를 탐색하는 데 필요한 시간 O(n)을 소비하지않기 위해 해쉬 테이블을 사용합니다

알고리듬

복잡도 분석

C++ 구현

---

방법 #3 - Math [Accepted]

아직 작성 중입니다.

---

방법 #4 - Bit Manipulation [Accepted]

아직 작성 중입니다.

이상입니다.