Table of contents

코딜리티 OddOccurrencesInArray

배열에서 쌍을 이룰 수 없는 요소를 찾는 문제이다. 이미 쌍을 이룬 요소는 검사에서 제외한다. (같은 값을 가진 요소와 쌍을 이룰 수 있음)

첫번째 풀이

public int solution(int[] A) {
    boolean[] checked = new boolean[A.length];
    for (int i = 0; i < A.length; i++) {
        if (checked[i]) continue;
        for (int j = i + 1; j < A.length; j++) {
            if (A[i] == A[j]) {
                checked[i] = true;
                checked[j] = true;
            }
        }
        if (!checked[i]) return A[i];
    }
    return 0;
}

이미 다른 요소와 쌍을 이루었는지 검사하기 위해 checked 배열을 사용했다. 2번의 반복문을 돌면서 현재 요소와 같은 값을 가진 요소가 없다면 해당 요소를 반환한다.

첫번째 풀이 결과

O(N**2) = O(N^2)

사이즈가 큰 배열에서 time out이 걸리고 하나의 테스트 케이스를 실패하여 55%의 결과가 나왔다.

두번째 풀이 (HashSet)

중복된 요소를 검사할 수 있는 HashSet을 사용할 수 있다. N이 HashSet에 이미 존재한다면 remove 하고 존재하지 않는다면 insert 한다. 쌍을 이루는 요소는 한번씩 insert, remove가 수행되어 제거되었으므로 최종 결과는 HashSet에 들어있는 요소를 반환한다.

세번째 풀이 (XOR)

XOR 연산자를 사용할 수 있다. 자바에서는 ^ 기호를 사용하며, 두 bit가 서로 다른 경우에만 1을 반환한다. 참고로 XOR은 비트의 특정 셋트를 반전하거나(선택적-보수 연산) 비트의 특정 셋트에 원하는 비트패턴을 삽입하는데(선택적-세트 연산) 사용할 수 있다.

  1. 선택적-보수 연산
    1. 10101 XOR 11111 = 01010
  2. 선택적-세트 연산
    1. 선택적-세트를 하기 위해서는 우선 특정 셋트를 리셋하기 위해 마스크 연산(0과 AND를 수행)을 수행한 뒤 삽입하길 원하는 비트패턴과 XOR 연산을 수행한다.
    2. 10111의 상위 3비트에 110 삽입
    3. 10101 AND 00011 = 00001
    4. 00001 XOR 11000 = 11001

다시 본론으로 돌아와서, XOR을 이용한 풀이는 다음과 같다.

  1. 결과값 변수를 0으로 초기화한다.
  2. 배열을 순회하면서 결과값과 현재 요소에 XOR 연산을 수행한다.
  3. 결과값 변수를 반환한다.
private int solution3(int[] A) {
    int result = 0;
    for (int i = 0; i < A.length; i++) {
        result ^= A[i];
    }
    return result;
}
  1. result = 0 -> 0000
    1. 9 -> 00000 xor 1001 = 1001 (9)
    2. 3 -> 1001 xor 0011 = 1010 (10)
    3. 9 -> 1010 xor 1001 = 0011 (3)
  2. 결과는 3 -> 0011

정리

XOR 연산이 보수화에 사용될 수 있으며 비슷한 원리를 이용해 값을 추가하고 같은 값은 제거할 수 있다는 것을 기억하자.

XOR 연산은 선택적-보수화와 선택적-셋트 연산 외에도 하이퍼 큐브의 E-큐브 라우팅, RAID의 패리티 등 컴퓨터시스템의 다양한 곳에서 사용된다.