중복 인덱스를 활용한 알고리즘

아래 문제는 코딜리티에서 제공하는 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.Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

문제 해결

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var result = Set<Int>()
    
    for i in A {
        if result.contains(i) {
            result.remove(i)
        } else {
            result.insert(i)
        }
    }
    
    return result.first!
}

사용된 개념

 - 배열

 - Set

 - 반복 / 조건문

문제 뒷담화

이번 문제는 짝을 지을 수 없는 요소를 찾는 문제였다.

우선 짝의 갯수 파악과 포함되어있는지를 확인하기 위해 빈 Set을 만들어준다.

중복요소를 허용하지 않게 해준다.

그 뒤 for문을 돌며 해당 Set에 인덱스 값이 포함되어 있다면 제거해주고 없다면 추가해준다.

최종적으로 1개의 중복짝이 없는 값만 들어 있을테니 첫번째 요소를 반환해주면된다.

이렇게 풀었는데..!

더 쉽게? 효율적으로? 푼 케이스를 구글링에서 발견했다.

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var result = 0
    
    for i in A {
        result ^= i
    }
    
    return result
}

바로 XOR 비트 연산을 해주는것이다.

사실 두 경우로 돌려봤을때 시간복잡도나 히든 테스트케이스가 모두 통과되고 같아서 어느게 효율적인지 확실친 않았다.

그렇지만 우선 코드의 조건문도 없어 아래 XOR연산이 더 효율적일거라 생각한다.

값이 같으면 0을 추가해주고 같지 않으면 1을 반환해준다.

9가 들어오고 3이 들어오면 같지 않아 1을 추가해줘서 10의 임시 값을 갖는다.

그 후 같은 값이 들어오면 0으로 바뀐다.

그렇게 전 배열을 돌면 하나만 가진 값이 들어가게된다.

사실 이 XOR 풀이법은 이해가 잘 되지 않았다.

실무에서도 저런 방법으로 많이 쓰일지도 궁금하다.

 

[참고자료]

https://app.codility.com/c/run/trainingCBB63V-2C8/

Codility