백준 Swift [10815] 숫자 카드

난이도

실버 V

 

문제

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

내 답안

let n = Int(readLine()!)!
let nCards = Set(readLine()!.split(separator: " ").map { Int($0)! })

let m = Int(readLine()!)!
let mNumbers = readLine()!.split(separator: " ").map { Int($0)! }

var isContain = [Int]()

for mNumber in mNumbers {
    nCards.contains(mNumber) ? isContain.append(1) : isContain.append(0)
}

print(isContain.map { String($0) }.joined(separator: " "))

- 주어진 항목들을 프로퍼티에 집어넣고, contains 메서드를 통해 isContain에 결과를 저장하여 출력하는 방식을 생각했다.

- 하지만 우려대로 시간 초과가 났고, Array의 contains는 O(n)인 반면 Set의 Contains는 O(1)이라는 것을 알게 되어 nCards의 타입만 변경해주었더니 통과가 되었다.

 

Array contains(_:) 

contains(_:) | Apple Developer Documentation

Set contains(_:) 

contains(_:) | Apple Developer Documentation

- 시간 복잡도의 차이가 나는 이유는, Array에서는 전체 항목을 다 확인해봐야 하기에 n만큼 걸리고, Set은 중복을 다 제거했기 때문에 동일한 다른 항목이 없고, Hashable하기 때문에 딱 그 항목이 들어있는지만 확인하면 되어 1이지 않을까 생각해본다.