[Codility] 3. 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.

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

 

int배열 A가 주어지고,

배열 내의 짝(pair)가 되는 값을 제외하고, 남은 짝이 없는 값을 찾는 문제다.

- 예시

A[0] = 9

A[1] = 3

A[2] = 9

A[3] = 3

A[4] = 9

A[5] = 7

A[6] = 9

위 배열이 주어진 경우 짝이 없는 값은 A[5] 이며, 해당 값인 7을 return하면 된다.

 

 

나는 이렇게 풀었다.

짝이 되는 두 값이 있다면, 결국 하나의 값만 남는 것이기 때문에

전체 sort를 해주고 다음 인자를 비교하여 값이 다르다면 해당 값을 리턴하기로 했다.

예시로 주어진 값의 경우

sort 하면,

A = {3, 3, 7, 9, 9, 9, 9} 가 된다.

A[0]과 A[1]를 비교하고 같으면 짝수만큼 이동해서 또 비교하는 방식으로 진행했다.

// 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) {
        // write your code in Java SE 8
        int result = 0;

        Arrays.sort(A);

        for(int i=0;i<A.length;i+=2){
            if(i+1 == A.length){
                result = A[i];
            }else if(A[i] != A[i+1]){
                result = A[i];
                break;
            }
        }
        
        return result;
    }
}

 

이전 문제의 함정을 교훈삼아

만약 A배열의 값이 하나만 들어오는 경우와 짝이 없는 값이 마지막 요소로 들어올 경우를 대비해서

(i+1 == A.length) 를 조건으로 걸어 주었다.

 

 

결과는

 

 

내가 푼 풀이가 맞는지 다른사람들의 풀이도 찾아보았다.

 

나처럼 푼 사람도 있었고

HashSet을 이용해서 동일 값을 찾아 추가,제거하며 찾는 방식을 쓴 사람도 있었다.

내 기준 신기했던 방식은 XOR을 이용해서 푼 방식이었다.

 

생각을 넓혀야겠다.