[Codility] OddOccurrencesInArray

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.

[문제풀이]

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int answer = 0;
        for(int i = 0; i < A.length; i++){
            if(i % 2 == 0){
                answer += A[i];
            }
            else{
                answer -= A[i];
            }
        }

        return answer;
    }
}

1. 문제에서 배열 자체가 0번째와 2번째, 1번째와 3번째.. 값이 같다고 주어지고있다.
2. 두 요소씩 짝지어지면 짝지어지지 않는 값이 남게된다.
3. Arrays의 sort 메소드를 이용하여 같은 요소끼리 정렬시킨다.
4. 앞에서부터 차례대로 리턴될 answer 값에 배열 A의 요소를 더해주고 빼준다.
5. 정수 i를 선언하고 배열 요소를 차례대로 더하고 빼다보면 짝지어지지 않은 값 하나만 남게된다.
   (ex. 문제에 예시로 나온 배열 A의 요소를 정렬하면 9,9,9,9,7,3,3 이렇게 되는데 차례대로 계산하면 9-9+9-9+7-3+3 = 7이 나온다. 즉 7을 리턴)