Leet Code - 136. Single Number(C++)

예제: Single Number

문제
Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

풀이

문제 자체는 참 간단하다.
한 번만 쓰인 숫자를 찾는것이다.

필자는 unordered_map을 사용하는 것(CASE1) 이 제일 빠르다고 생각해서 풀어봤는데, 생각보다 속도가 별로였다.

다른 좋은 방법으로는 bit연산 중 XOR을 사용하는 방법(CASE2)이 있어서, 참고해서 풀어보았다. 역시 bit연산은 잘 쓰기만 하면 엄청나게 빠른 것 같다. 익숙하지가 않아서 그렇지😅

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE1 */
class Solution {
public:
	int singleNumber(vector<int>& nums) {
		unordered_map<int, int> um;

		for (int i = 0; i < nums.size(); i++) {
			um[nums[i]]++;
		}

		for (auto itr = um.begin(); itr != um.end(); itr++) {
			if (itr->second == 1) return itr->first;
		}

		return 0;
	}
};


/*CASE2*/
class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int res = 0;

		for (auto& num : nums) {
			res ^= num;
		}

		return res;
	}
};

풀이 후기

bit연산을 자주 접할 기회가 없다보니, 바로 떠오르지가 않았다. 그래도 이 문제는 비교적 bit연산을 적용하기 쉬운 문제였지만, 높은 난이도의 문제를 풀려면 bit연산에 좀 더 익숙해져야겠다.