Codility Lesson 2: OddOccurrencesInArray

minin·2022년 5월 2일
0

Algorithm

목록 보기
6/12
post-thumbnail

문제 분석

  • 홀수 개의 원소를 가진 Int Array A를 가져와, 짝이 없는 숫자를 리턴한다.

ex) A = [9, 3, 9, 3, 9, 9, 11]

  • 짝이 없는 숫자는 11
  • 11을 리턴

방법1

  • 원소를 pop하여 value에 저장
  • 배열에 여전히 value가 있는지 검색
  • 있으면 지우고, 없으면 해당 값을 return
public func solution(_ A : inout [Int]) -> Int {
    // non-empth array, N개 int
    // 하나의 odd넘버,

    for _ in A {
        if let value = A.popLast() {
            print("\(value)의 짝 찾기")
            if let pairIndex = A.firstIndex(of: value) {
                print("\(value)의 짝은 \(A[pairIndex])")
                A.remove(at: pairIndex)
            } else {
                print("\(value)의 짝은 없음")
                return value
            }
        }
    }
    
    return 0
}
  • 위의 함수도 동작은 하지만, 배열의 크기가 커졌을 때는 실행시간 초과가 나왔다.



방법2

  • 배열을 순서대로 정렬한 다음에 2칸씩 이동하면서 짝이 없는 것 찾기
  • 짝이 없는 수가 가장 마지막에 왔을 때 예외처리
public func solution(_ A : inout [Int]) -> Int {
    
    let sortedA = A.sorted()
    print(sortedA)
    for idx in stride(from: 0, to: A.count-1, by: 2) {
        print(sortedA[idx])
        if sortedA[idx] != sortedA[idx+1] {
            return sortedA[idx]
        }
    }
    // 짝이 없는 수가 가장 마지막에 왔을 때는 마지막 원소를 리턴
    return sortedA.last!
}



방법3

  • XOR^ 연산자 ?
  • XOR: 같으면 false, 다르면 true
let firstBits: UInt8 = 0b1110110
let secondBits: UInt8 = 0b1111111
let resultBits = firstBits ^ otherBits	// 0001001
public func solution(_ A : inout [Int]) -> Int {
    var temp = 0
    
    for item in A {
        temp = temp^item
    }
    
    return temp
}

🔖 참고

profile
🍫 iOS 🍫 Swift

0개의 댓글