OddOccurrencesInArray

🔗 문제 링크

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/start/

❔ 문제 설명

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:

def solution(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.

⚠️ 제한사항

• 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.

💡 풀이 (언어 : Java)

sort는 시간 복잡도가 $O(N*logN)$ 정렬해서 같은 숫자끼리 모으고 두개씩 짝지어서 계속 비교한다. 정답인 수 말고는 다 짝수 개수이므로 짝지은 수중에 다른 수가 나오면 무조건 앞의 숫자가 정답인 수이다.

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        // 길이가 1이면 유일한 원소가 답
        if (A.length == 1)
            return A[0];
        // 같은 숫자끼리 모이도록 정렬
        Arrays.sort(A);
        // 두개씩 단독으로 짝지어서 조회 
        for (int i = 0; i < A.length; i+=2) {
            // 짝지은 숫자끼리 다르면 앞의 숫자가 정답
            // 정답 숫자 빼고는 모두 짝수라 다른 수는 무조건 앞에 온다.
            // 마지막 원소전까지 통과하면 마지막 원소가 정답
            if (i == A.length-1 || A[i] != A[i+1])
                return A[i];
        }
        // 여기는 문법상 적은 return이고 여기로 빠질 수는 없다.
        return 0;
    }
}