OddOccurrencesInArray

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

OddOccurrencesInArray coding task - Learn to Code - Codility

 

홀수개의 원소를 가진 배열에서, 짝을 이루지 못한 숫자를 찾아야 한다.

 

 List나 Map을 사용해서 짝을 찾는 방법을 쓸까 했는데,

 

그러면 배열을 순회하면서 contains, add, remove를 써야해서 귀찮을거 같았다.

 

그래서 원소들을 오름차순 정렬해두고, 

 

n번째와 n+1번째의 숫자가 같지 않으면 n번째 숫자가 짝을 이루지 못했다는 의미이므로

 

// 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) {
        // Implement your solution here

		// 원소 갯수가 1개라면 비교할 필요도 없다.
        if (A.length < 3) return A[0];

		// 우선 오름차순 정렬하고,
        Arrays.sort(A);

		// n - 1번째까지의 원소가 모두 짝을 이루었다면 n번째 원소가 짝을 이루지 못한 숫자임
        int answer = A[A.length - 1];
        // i를 2씩 증가시켜야하고, 마지막 원소까지가면 안되므로..
        for (int i = 0; i < A.length - 1; i = i+2) {
            if (A[i] != A[i+1]) {
                answer = A[i];
                break;
            }
        }

        return answer;

    }
}