Swift - 백준 1764번 듣보잡

Dictionary를 사용하는 것보다 되도록이면 간단한 자료형을 사용하는 것이 효율적일 수 있습니다

 

 

Dictionary 시간초과 코드

Dictionary로 코드를 구현하였다가 시간초과가 발생하였습니다. Dictionary로 Key 값과 Value 값으로 문제를 해결하려다 보니 불필요한 Value값을 지속적으로 contains를 통해 검사해야 했고 이는 효율적이지 못했습니다.

import Foundation

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

var arr: [String] = []
var arr2: [String] = []
for _ in 1...count[0] {
    arr.append(readLine()!)
}

for _ in 1...count[1] {
    let tmp = readLine()!
    if arr.contains(where: { $0 == tmp } ) {
        arr2.append(tmp)
    }
}

print(arr2.count)
arr2.forEach({ str in
    print(str)
})

 

String 배열로 인한 시간초과

다음은 String 배열을 사용하였지만 시간초과가 발생한 코드입니다. 하지만 중복되는 사람들의 이름이 중복적으로 배열에 추가되어 메모리에 부화를 일으키는 것을 확인하여 Set를 사용하게 되었습니다.

 

 

Set를 사용한 문제 해결

다음 Set는 중복을 허용하지 않는 자료형으로 문제를 해결하는데 적합하였습니다.

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

var arr = Set<String>()

for _ in 1...line[0] {
    arr.insert(readLine()!)
}

var arr2 = Set<String>()

for _ in 1...line[1] {
    let tmp = readLine()!
    if arr.contains(tmp) {
        arr2.insert(tmp)
    }
}

print(arr2.count)
arr2.sorted().forEach { print($0) }