Codility_OddOccurrencesInArray

2-2. OddOccurrencesInArray

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.

주어진 배열에서 짝이 맞지 않는 값을 찾는 문제입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        // Implement your solution here
        HashMap<Integer, Integer> map = new HashMap<>();
        int result = 0;

        for (int value : A) {
            map.put(value, map.getOrDefault(value, 0) + 1);
        }

        for (int key : map.keySet()) {
            if (map.get(key) == 1) {
                result = key;
                break;
            }
        }

        
        return result;
    }
}

해시맵을 사용해서 기존 배열의 값을 키로 만들고 동일한 값이 있을경우 맵에서는 값을 +1하여
최종적으로 맵에서 값이 1인 키값이 짝이 맞지 않는 것을 알 수 있습니다.

위 방법이외에 찾아보니 비트연산을 통해 문제를 푸는 방법도 있어 해당 방법도 공유합니다.

비트연산을 통한 문제 풀이 ->

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int result = 0;
        
        for (int value : A) {
            result ^= value;
        }
        
        return result;
    }
}

이 코드는 XOR 연산을 사용하여 배열에서 유일한 요소를 찾습니다.
XOR 연산의 특성상 동일한 숫자가 두 번 XOR되면 0이 되므로, 유일한 요소만 남게 됩니다.
이 방법은 시간 복잡도가 O(n)이고, 공간 복잡도가 O(1) 이므로 기존 작성했던 코드보다 매우 효율적입니다.

문제 풀어보기 ->
https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/