[codility] OddOccurrencesInArray

(문제) 홀수 개의 원소를 가지는 배열(Non-Array)에서 짝이 없는(non-paired) 원소 값을 반환하는 함수 작성

 

(my solution)

- 배열에서 짝이 있는 지 없는 지를 어떻게 판별할 건지?가 문제의 키 포인트였다.

- HashSet을 활용하여 Array를 모두 방문하고도 끝까지 남아있는 원소를 반환하는 방식으로 함수를 작성하였다.

- 따라서 시간복잡도는 최소, 최대, 평균 모두 O(N)이다. 무조건 배열의 원소 끝까지 방문해야 짝이 없는 원소 값을 찾을 수 있다.

- IntelliJ의 자동 완성 기능을 이용하여 개발하다보니 HashSet을 import할 때라던 지, 마지막 리턴문을 작성하기 어려웠다;

- 다른 문제풀이 방법으로는 1) 정렬 후 2) 짝이 없는 원소 값을 찾는 방법도 있다. 하지만 시간 복잡도가.. 퀵 정렬을 쓰더라도 1) O(NlogN) + 2) 최대 O(N) = O(N + NlogN)

package codility.tasks;

import java.util.HashSet;

public class OddOccurrencesInArray {
    public static int solution(int[] A) {
        HashSet<Integer> founded = new HashSet<>();

        for (int i = 0; i < A.length; ++i) {
            if (founded.contains(A[i])) {
                founded.remove(A[i]);
            } else {
                founded.add(A[i]);
            }
        }

        return (int) founded.toArray()[0];
    }
}

 

 

(chatGPT) - 와.. 미친..

- XOR의 성질을 이용하여 짝이 있는 데이터는 상쇄시키고, 짝이 없는 나머지만 반환했다.

- 코드가 매우 심플하다. 시간복잡도는 O(N)

- unpaired를 0으로 초기화해야 하는 것에 유의해야 한다. (배열의 첫번째 원소 값을 변형 없이 그대로 유지하기 위해서)

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

 

*비트연산자 XOR (^)

두 비트가 같으면 0, 다르면 1을 반환한다.