[Swift 알고리즘] Codility lesson2 - OddOccurrencesInArray

안녕하세요 코코종입니다!

 

오늘은 OddOccurrencesInArray라는 문제를 풀어봤는데요!

홀수개의 원소를 가지는 Array에서 단 한가지 요소만 짝을 이루지 못하는데 그 원소를 찾아내는 문제였습니다.(솔로 찾기..!)

public func solution(_ A : inout [Int]) -> Int {
    var stack: [Int] = []
    let arr: [Int] = A

    arr.forEach { a in
        if !stack.contains(a) {
            stack.append(a)
        } else {
            stack = stack.filter{ $0 != a }
        }
    }

    return stack.first!
}

처음에는 단순히 Stack에 해당 원소의 유무에 따라 append와 remove를 해준건데요

네,... 시간초과가 나왔습니다 ㅋㅋㅋ  'O(N**2) 으로도 되나..?' 했는데 어림도 없습니다.

어림도 없다 암!

그래서 바로 복잡도를 줄일 생각을 해봤는데요. 일단 contains나 filter를 거치면서 복잡도가 확 올라가는걸 어떻게 줄일까 했는데

제일 간단하게 떠오른게 Array -> dictionary 였습니다.

결국 마지막에는 딕셔너리에 한쌍의 key-value만 남기 때문에 keys의 first를 답으로 return 했습니당

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ A : inout [Int]) -> Int {
    var dict: [Int:Int] = [:]
    let arr: [Int] = A

    // dict 에 적재(1개만 남음)
    arr.forEach { a in
        if dict[a] == nil {
            dict[a] = a
        } else {
            dict[a] = nil
        }
    }

    return dict.keys.first!
}

 

간단한 문제였는데 복잡도를 생각하지 않아서 틀렸던..! 문제였습니당