7785번: 회사에 있는 사람

추가 / 삭제가 O(1)인 자료형

주어진 문제는 어떤 자료형에 주어진 String을 넣었다가 빼는 일을 자주 수행해야 합니다. 많이 사용하는 Array의 경우 append는 O(1)이지만 remove의 경우 O(n)의 시간복잡도를 가지므로 시간초과가 날 가능성이 높습니다.

Array는 index로 접근하는 것이 O(1)인 대신 remove하는 경우 배열의 모든 element를 돌면서 해당 element를 찾아서 삭제하고 삭제한 이후에도 element들을 순서대로 다시 저장해야하기 때문입니다.

스위프트에서 추가, 삭제가 O(1)인 자료형은 set과 dictionary가 있습니다. 두 자료형은 각각 element와 key가 Hashable해야 합니다. 따라서 자료의 hash 값을 통해서 O(1)의 시간 복잡도로 추가 삭제가 가능한 것입니다.

Set을 이용한 풀이

// 이름을 저장할 Set을 선언
var set = Set<String>()

let N = Int(readLine()!)!

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { String($0) }
    if input[1] == "enter" { // enter면 insert
        set.insert(input[0]) //👉 O(1)
    } else { // leave면 remove
        set.remove(input[0]) //👉 O(1)
    }
}

//⭐️ Set을 정렬하면 Array로 바뀝니다. (sorted 메소드의 리턴 값이 Array이기 때문)
set.sorted(by: >).forEach { name in
    print(name)
}

Dictionary를 이용한 풀이

// 이름을 저장할 Dictionary를 선언
var dict = [String : Bool]()

let N = Int(readLine()!)!

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { String($0) }
    if input[1] == "enter" {
        dict[input[0]] = true //👉 O(1)
    } else {
        dict[input[0]] = nil //👉 value에 nil을 할당하면 데이터가 삭제됨 = O(1)
    }
}

//⭐️ Dictionary의 keys 속성을 활용하면 key만 배열로 가져올 수 있음
dict.keys.sorted(by: >).forEach { name in
    print(name)
}