1302번: 베스트셀러

사용할 자료형: Dictionary

입력이 들어올 때 마다 데이터에 접근해서 판매량을 + 1 해주어야 합니다. 따라서 데이터에 접근할 때 O(1)인 자료형을 찾아야 합니다. Dictionary와 Set이 있는데 그 중에서 key-value의 쌍으로 이루어져서 책이름-판매량으로 저장하기 좋은 Dictionary를 사용합니다.

풀이

// 판매 실적을 저장하기 위한 Dictionary
var sales = [String: Int]()

let N = Int(readLine()!)!

for _ in 0..<N {
    let book = readLine()!
    if sales[book] != nil { //👉 이미 팔린 적이 있는 책이면
        sales[book]! += 1 //👉 기존 판매량에 +1
    } else { //👉 그렇지 않다면
        sales[book] = 1 //👉 1권 판매
    }
}

var bestSeller: String = ""
var bestSales = 0

for book in sales.keys { //👉 책을 순회하면서
    if sales[book]! > bestSales { //👉 지금 책 보다 많이 팔렸다면?
        bestSeller = book //👉 bestSeller 갱신하고
        bestSales = sales[book]! //👉 판매량도 갱신
    } else if sales[book] == bestSales { //👉 지금 책과 동일하게 팔렸다면?
        bestSeller = bestSeller < book ? bestSeller : book //👉 지금 사전 순으로 앞서는 것이 bestSeller
    }
}

print(bestSeller)

코드 다이어트🏃‍♂️

dictionary가 제공하는 기능들을 활용해서 코드를 더 슬림하게 만들어 봅시다.

// 판매 실적을 저장하기 위한 Dictionary
var sales = [String: Int]()

let N = Int(readLine()!)!

for _ in 0..<N {
    let book = readLine()!
    if sales.keys.contains(book) { //👉 keys에 해당 key가 있는지 확인하는 메소드 O(1)
        sales[book]! += 1
    } else {
        sales[book] = 1
    }
}

var bestSellers = [String]()
let bestSale = sales.values.max()! //👉 keys와 마찬가지로 values도 따로 모아서 볼 수 있음.

for book in sales { //👉 dictionary도 반복문의 대상이 될 수 있음
    if book.value == bestSale { //👉 .value로 value에 접근
        bestSellers.append(book.key) //👉 .key로 key에 접근
    }
}

print(bestSellers.sorted()[0])

sales.keys.contains(book)이 정말로 O(1)인가요?

sales.keys의 리턴값이 Array라면 contains 메소드는 O(n)일 것입니다. 하지만 리턴값은 Keys라는 Sequence 타입의 또 다른 자료형입니다. 그리고 이 타입의 contains 메소드는 O(1)이라고 합니다. 실제로 sales[book] != nil을 사용한 풀이와 시간을 비교해도 동일하게 나오는 것을 볼 수 있습니다.

참고한 블로그

백준 Swift 1302번, 11047번, 1449번, 11724번, 2178번, 7785번, 1021번, 1158번, 2346번, 1406번, 1935번, 1874번, 1764번, 10799번, 2304번, 2841번, 3986번, 1966번

keys.contains()가 O(1)인가?

Does Dictionary.Keys.contains(_:) have O(1) time complexity?