Lesson 2(Iterations) - 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.

 

홀수개의 정수로 이루어진 배열을 제공하면 배열 안에 짝이 되지 않는 값을 찾는 문제입니다.

 

 풀이

 

1차 적용

    import java.util.Arrays;

    public static int solution(int[] A) {
    	// write your code in Java SE 8
        int res = 0;
        Arrays.sort(A);

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

정렬 후 앞과 뒤 중 같은 값이 없으면 Solo로 판단하고 그 값을 반환하였습니다.

제출 결과 70점을 받았습니다 ㅠㅠ

* 이슈

A = {9,9,9} 인 경우처럼 동일한 숫자가 페어와 솔로가 같이 있는 경우 오답이 나왔습니다.

쉽게 생각을 바꿔 전부 페어인 곳 중에 솔로는 항상 홀수번째에 위치하고 다음 값과 비교하여 다를 경우 그 값을 찾는 방법으로 구현하였습니다.

import java.util.Arrays;

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

        return A[A.length-1];
    }
}

 

 결과

주소 : app.codility.com/demo/results/trainingA36624-6FW/

 

정확도와 성능 모두 100점 받았습니다.