[알고리즘] codility OddOccurrencesInArray 문제

문제 : 

N개의 정수로 구성된 배열 A가 있는데 이 배열은 홀수 개의 원소들을 가지고 있다. 그리고 딱 한 원소를 제외한, 나머지 원소들은 다른 원소와 같은 값을 가지고 짝을 이룬다. 여기서 짝을 이루지 않는 원소를 알아내라.

{9,3,9,3,9,7,9} 에서는 7이 짝을 이루지 않는 원소이다.

---

처음에 나는 o(n)2 의 시간 복잡도를 가진 알고리즘을 작성했다. for 문을 두 번 돌려서 똑같은 숫자가 있다면 -1로 값을 바꾸고 -1이 아닌 값들을 특정 변수에 저장하도록 해서 문제를 풀었는데 시간 초과로 점수가 66점을 맞았다. o(n)2 알고리즘 밖에 생각이 안나서 결국 구글을 했는데 xor을 사용하라는 어떤 블로그를 보았다. 

public class OddOccurrencesInArray {
	public static void main(String[] args) {
		int aa[] = {9,3,9,3,9,7,9};
		
		System.out.println(solution(aa));
	}
	
	public static int solution(int[] A) {
		
		int temp = 0;
		
		for(int i= 0; i<A.length; ++i){
			temp = temp ^ A[i];
			System.out.println("xor : "+temp);
		}
		return temp;
	}
	
	// 시간 복잡도 실화냐?
}

먼저 XOR 은 비트 연산자이다. 그래서 2진수로 계산을 하는데 둘이 값이 다르면 1이고, 둘의 값이 같으면 0이다.

예를 들어보겠다.

1^2 를 했을 때 1=0001, 2=0010 이다. 그래서 XOR 연산을 하면 닶은 0011이 된다.

그렇다면 위의 코드에서 XOR 연산했을 때의 과정을 보도록 하겠다.

0000 1001 = 1001 = 9

1001 0011 = 1010 = 10

1010 1001 = 0011 = 3

0011 0011 = 0000 = 0

0000 1001 = 1001 = 9

1001 0111 = 1110 = 14

1110 1001 = 0110 = 7

temp 변수는 처음에 0으로 초기화를 시켜줬기 때문에 0000으로 시작한다.

결국 똑같은 수들을 제외해서 나온 값은 외톨이 7이다. 문제 조건을 잘 확인하자 짝이 맞는 수가 있고 없고의 차이다. 

HashSet 을 이용해서 쉽게 해결할 수도 있다. 

Set은 집합적인 개념의 Collection 으로 순서의 의미가 없지만 Data를 중복해서 포함할 수 없는 특징을 가지고있다.

그러면 HashSet의 특징으로는 add() 메소드를 이용해 데이터를 삽입, next()를 이용해 데이터를 추출 할 수 있다.

또한, Iterator를 이용해서 추출할 수가 있다.

	public static int solution(int[] A) {
		
		Set<Integer> set = new HashSet<>();
		
		for(int i : A){
			if(set.contains(i)){
				set.remove(i);
			}else{
				set.add(i);
			}
		}

		return set.iterator().next();
	}