[Codility] OddOccurrencesInArray 55점→100점

문제 출처 : https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

문제요약 : 배열요소중에서 짝이 없는 요소의 값을 출력해라

[55점] O(n**2)

처음 접근 방식은 모든배열의 요소를 돌면서 같은 숫자가 있으면 count라는 변수값을 증가 시키고.

최종적으로 1개만 있는 경우를 return해주게했다.

결과는 10만건이상의 데이터가 들어왔을때 TimeOut이 발생했다.. ㅎㅎㅎ 심지어 코드도 지저분..

package test_java2;
 
import java.util.*;
 
 
public class Main {
 
    public static void main(String[] args) {
        int[] a = {2,2,3,3,4};
        int result = solution(a);
        System.out.println(result);
    }
    
    public static int solution(int[] A) {
        int now=0;
        int count=0;
        for(int i=0 ;i<A.length;i++) {
            now = A[i];
            for(int j=0;j<A.length;j++){
                if(now==A[j]){
                    count++;
                }
            }if(count<2) {
                return now;
            }
            count=0;
        }
        return now;
    }
 
}//CALSS END
 

[100점] O(N)

Set의 속성을 이용하면 의외로 간단한 문제였다. 

구글링해보니 XOR연산자를 이용하면 훨씬 간결한 코드가 작성된다.

package test_java2;
 
import java.util.*;
 
 
public class Main {
 
    public static void main(String[] args) {
        int[] a = {2,2,3,3,4};
        int result = solution(a);
        System.out.println(result);
    }
    
    Set<Integer> set = new HashSet<Integer>();
        for(int temp : A) {
            if(set.contains(temp)?set.remove(temp):set.add(temp));
        }
        return set.iterator().next();
 
}//CALSS END