[Codility(코딜리티)] Lesson2. OddOccurrencesInArray (100%)

Lesson 2 Arrays - OddOccurrencesInArray (Java Solution)

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

OddOccurrencesInArray coding task - Learn to Code - Codility

 

---

문제

홀수개의 배열 A가 주어진다

예를 들면, A = {9,3,9,3,9,7,9}

여기서 9는 4개, 3은 2개, 7은 1개이다

짝이 없는 숫자를 출력하면 된다

즉, 7이 정답이다

 

해결

Map을 하나 만든 후, 배열의 값을 Key로 하여 개수를 Value로 넣었다

Key가 비어있으면 1로 처음에 넣어주고, 있으면 1씩 더한다

public class OddOccurrencesInArray {
    public int solution(int[] A) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int result = 0;

        for (int i=0; i<A.length; i++) {
            map.computeIfPresent(A[i], (key, value) -> ++value);
            map.putIfAbsent(A[i],1);
        }

        for (Integer key : map.keySet()) {
            int value = map.get(key);
            if (value % 2 == 1) {
                result = key;
                break;
            };
        }
        return result;
    }
}

자바 11에선 100%로 통과하였지만, 

 

자바 8에선 시간 초과로 88%가 나왔다 (왜지..)

비트연산 XOR 풀이

다른 사람들의 풀이를 찾아보다가 전혀 생각못한 풀이가 하나 있어서 정리해보려고 한다

이 문제는 결국 짝수가 아닌 배열의 값을 구하는 것이다

따라서 XOR 비트연산을 이용하면,

두 값이 서로 다를 경우 참(1)이고, 같으면 거짓(0)이다

즉, A = {9,3,9,3,9,7,9}를 모두 비트연산하면,

1001 0011 1001 0011 1001 0111 1001,

같은거 끼리 먼저 비트연산을 하면 모두 0000이 되고, 결국 0111(7)이 남는다

public int solution(int[] A) {

  int result = 0;

  for (int i=0; i<A.length; i++) {
  	result = result ^ A[i];
  }

return result;

시간복잡도 O(N)으로 아주 깔끔하게 풀렸다