[Codility] Lesson 2 : OddOccurrencesInArray - JAVA

문제

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–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 배열 A의 범위는 1 ~ 1,000,000,000이고,
배열 A에 Element로 들어가는 홀수의 범위는 1 ~ 1,000,000이다.

배열 A의 Element 중 하나는 중복된 값을 갖지 않으며, 나머지 숫자들은 배열 A 안에서 중복된 값을 갖는다.

    ex) A[0] = 9 A[1] = 3 A[2] = 9
          A[3] = 3 A[4] = 9 A[5] = 7
          A[6] = 9

예제의 A 배열에서 index 0과 2, 4와 6은 숫자 9를 가지고 있으며 쌍을 이룬다.
그리고 index 1과 3은 숫자 3을 가지고 있으며 쌍을 이루지만,
index 5는 숫자 7을 가지며 쌍을 이루지 않는다.

'solution' Method를 구현하여 쌍을 이루지 않는 홀수를 찾아 결과 값으로 반환한다.

 

풀이 - 1

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
class Solution {
    public int solution(int[] A) {
        if(A.length == 1) return A[0];
        Map<Integer, Boolean> pairMap = new HashMap<Integer, Boolean>();
        for(int subA : A) {
            pairMap.put(subA, pairMap.containsKey(subA));
        }
        if(pairMap.size() == 1) return A[0];
        Iterator<Integer> keys = pairMap.keySet().iterator();
        int unPairNum = 0;
        while(keys.hasNext()) {
            int key = keys.next();
            if(!pairMap.get(key)) {
                unPairNum = key;
                break;
            }
        }
        return unPairNum;
    }
}

 

'풀이 - 1'에 대한 회고

 

먼저 시도해 본 소스코드는 Map을 이용해 중복되지 않는 값을 찾는 것!

배열에 있는 홀수를 HashMap의 Key로 사용하고, HashMap에 Key 값이 존재하면 value에 true 값을 저장해준다.

그러면 쌍을 이루지 않는 값만 value로 false 값을 갖는다.

 

그렇게 시도한 첫 번째 결과는 처참하다.

Time spent가 67 min이 나왔다.

(참고로 몇 분뒤 같은 코드로 다시 실행해봤는데 1 min이 나왔다.)

 

그리고 중요한 것은 Score!

66%가 나왔다.

 

 

Codility에서 정확성과 퍼포먼스를 통해 Score를 채점해준다.

그런데 정확성이 80%, 퍼포먼스가 50%.

조금 더 효율적인 알고리즘을 생각해봐야겠다.

 

풀이 - 2

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class Solution {
    public int solution(int[] A) {
        if(A.length == 1) return A[0];
        List<Integer> aList = new ArrayList<Integer>();
        for(int subA : A) {
            aList.add(subA);
        }
        if(aList.stream().distinct().count() == 1) return A[0];
        List<Integer> result = aList.stream().filter(n -> Collections.frequency(aList, n) == 1).collect(Collectors.toList());
        return result.get(0);
    }
}

 

'풀이 - 2'에 대한 회고

 

'풀이 - 1'과 전혀 다른 방법으로 문제를 해결해보려고 Stream을 사용해봤다.

먼저 Stream을 이용하기 위해 배열 A를 리스트로 바꿔주었다.

그리고 Collections.frequency(...)를 이용해서 중복된 값이 없는 Element를 찾아낸다.

 

물론 '풀이 - 1'에 비해 비해 소스코드의 길이는 줄어들었다.

그러나 문제는 결과!

Time spent가 5 min이 나왔지만 크게 의미없다!

Score가 44%로 떨어졌다.

 

 

그래서 Score가 왜 떨어졌는지 확인해보니...

퍼포먼스가 아예 안나오네?

Stream을 사용해도 퍼포먼스가 조금 나올 줄 알았는데 더 안좋아졌다.

두 번째 테스트 코드는 폭망!

퍼포먼스가 조금 덜 나와도 '풀이 - 1'이 더 효율적이다!

 

풀이 - 3

import java.util.HashSet;
class Solution {
    public int solution(int[] A) {
        HashSet<Integer> aSet = new HashSet<Integer>();
        for(int subA : A) {
            if(aSet.contains(subA)) aSet.remove(subA);
            else aSet.add(subA);
        }
        return aSet.iterator().next().intValue();
    }
}

 

'풀이 - 3'에 대한 회고

 

Stream을 테스트 해보기 전에 HashSet을 이용해서 풀면 해결되지 않을까 생각했다.

그래서 Stream이 망한걸 보고 바로 시도!

결론부터 말하면 '이게 답이다'!

 

먼저 문제를 잘 보면 숫자 9가 4개가 있다.

그런데 왜 index 0과 2가 하나의 Pair이고, index 4와 6이 하나의 Pair라고 했을까?

그 말은 index 0과 2가 이미 한 쌍을 이루고 있기 때문에

index 2와 4가 중첩되서 Pair를 이룰 수 없다는 것을 의미하는 것 같다.

결국 중복되지 않는 숫자를 빼면 다른 숫자들은 배열 안에 2n개씩 들어있다는 의미이다.

 

그리서 HashSet에 중복되는 값이 있으면 HashSet에서 그 값을 지워줬다.

예제로 사용된 배열 A를 통해 조금 더 자세히 알아보면...

처음 HashSet에는 아무 값도 들어있지 않다. 9 3 9 3 9 7 9

A[0]의 값(9)이 HashSet에 없기 때문에 HashSet에 값을 추가해준다.           →    HashSet : [9]
A[1]의 값(3)이 HashSet에 없기 때문에 HashSet에 값을 추가해준다.           →    HashSet : [9, 3]
A[2]의 값(9)이 HashSet에 이미 존재하기 떄문에 HashSet에서 지워준다.    →    HashSet : [3]
A[3]의 값(3)이 HashSet에 이미 존재하기 떄문에 HashSet에서 지워준다.    →    HashSet : []
A[4]의 값(9)이 HashSet에 없기 때문에 HashSet에 값을 추가해준다.           →    HashSet : [9]
A[5]의 값(7)이 HashSet에 없기 때문에 HashSet에 값을 추가해준다.           →    HashSet : [9, 7]
A[6]의 값(9)이 HashSet에 이미 존재하기 떄문에 HashSet에서 지워준다.    →    HashSet : [7]

 

이 과정을 반복하면 쌍을 이루지 못한 숫자 하나만 남게된다.

이 값을 꺼내서 반환해주면 끝!

 

 

HashMap을 사용한 소스코드보다 더 효율적인 성과를 얻을 수 있다.

정확도도 100%, 퍼포먼스도 100%.

이제 다른 사람들이 풀이한 

 

다른 사람의 풀이

class Solution {
    public int solution(int[] A) {
        int result = 0;
        for(int subA : A) {
            result ^= subA;
        }
        return result;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

HashSet을 통해 문제가 해결되서 좋아하며 다른사람의 코드를 찾아보았다.

'풀이 - 1'과 '풀이 - 3'의 방식으로 푼 사람들을 보며 '음~ 비교적 잘 했구만!' 이라고 생각하고 있었는데

저 문제풀이를 보며 머릿 속에서는 '아...' 라는 단어밖에 떠오르지 않았다.

찾아보니 '풀이 - 3'의 시간복잡도는 O(n), 공간복자도도 O(n).

다른 사람의 풀이는 시간복잡도는 O(n), 공간복자도도 O(1)라고 한다.

 

복잡도에 대해서는 개별적으로 공부하고!

 

다른 사람의 풀이를 설명하면...

먼저 XOR(^)이라는 비트연산자를 이용하였다.
XOR 연산자는 비교할 두 숫자를 2진수로 바꿔서 각 자리의 값이 같으면 0으로, 다르면 1로 계산한다.
예를 들어 숫자 1은 2진수로 0001이고 숫자 2는 이진수로 0010이다.
이 두 2진수를 XOR로 비교하면 아래와 같이 2진수 0011 값을 반환하게 된다.
    1       →      0001
    2       →      0010
    ----------------------
    XOR(1^2)   0011

이 비트연산자를 이용해서 예제로 작성된 배열에 적용하면
    result 값(0)과 A[0]의 값(9)을 XOR 연산해준다.   → 0000 ^ 1001 → 1001(10진수 9이므로 result에 9 저장)
    result 값(9)과 A[1]의 값(3)을 XOR 연산해준다.   → 1001 ^ 0011 → 1010(10진수 10이므로 result에 10 저장)
    result 값(10)과 A[2]의 값(9)을 XOR 연산해준다. → 1010 ^ 1001 → 0011(10진수 3이므로 result에 3 저장)
    result 값(3)과 A[3]의 값(3)을 XOR 연산해준다.   → 0011 ^ 0011 → 0000(10진수 0이므로 result에 0 저장)
    result 값(0)과 A[4]의 값(9)을 XOR 연산해준다.   → 0000 ^ 1001 → 1001(10진수 9이므로 result에 9 저장)
    result 값(9)과 A[5]의 값(7)을 XOR 연산해준다.   → 1001 ^ 0111 → 1110(10진수 14이므로 result에 14 저장)
    result 값(14)과 A[6]의 값(9)을 XOR 연산해준다.  → 1110 ^ 1001 → 0111(10진수 7이므로 result에 7 저장)

 

결국 쌍을 이루는 숫자들은 0을 반환하게 되고, 쌍이 없는 숫자는 자신을 반환하기 때문에

조금 더 효율적으로 결과를 찾을 수 있게된다.

 

※ 아직 더 많이 공부해야겠다.

※ 분명 알고리즘에 더 익숙해지면 나도 저렇게 문제 해결을 할 수 있겠지!!??