[알고리즘] #Single Number

출처: https://leetcode.com/problems/single-number/

Single Number - LeetCode

문제

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

 

 

풀이

한 개를 제외한 나머지 원소들의 값이 2개씩 중복되는 값들로 이루어져 있는 배열에서, 중복되는 값이 없는 하나의 원소 값을 구하는 문제이다. 시간복잡도와 메모리 사용에 대해 고민을 했어야 했다.

그래서 먼저 배열을 오름차순으로 정렬한 뒤, 2개씩 더해가면서 비교하는 방법으로 풀어보았다.

그랬더니 통과했다.

 

그런데 runtime이랑 memory 사용이 다른 사람들이 제출한 코드보다 좀 떨어져있었다.

그래서 다른 사람들이 짠 코드는 어떤가..하고 봤는데

 

runtime 1등 코드

메모리효율성 1등 코드

 

역시 코드 라인 수부터 다르구나..^^...나는 아직 멀었구나...

 

일단 runtime 1등 코드를 보면, 첫 번째 원소를 기준으로 마지막 원소까지 순회하면서 비트 연산(XOR)을 이용해 중복되지 않은 수를 구했다.

XOR 연산에 대해 간단히 알아보면 아래와 같다.

a	b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

즉 비교할 두 값이 같으면 0을 리턴하고, 하나의 값과 0을 XOR 연산하면 본인 값이 나온다. 이 연산 결과를 이용해 문제를 풀었던 것이다.

for 문을 돌면서 모든 원소에 대해 XOR 연산을 실행하면, 결국 결과 값은 중복되지 않은 원소 값이 리턴된다.

 

메모리 효율성 1등 코드를 보면, indexOf 메서드를 이용해서 첫 인덱스 값과 마지막 인덱스 값이 같으면 중복이 없는 원소이므로 이를 리턴해준다. 별도의 변수를 생성하지 않고, 메서드 결과 값을 이용해서 결과를 리턴해줬다.

 

 

비트 연산은 정말 생각도 못했는데... 기억해뒀다가 꼭 써먹어야지!!!!!