첫번째 버전
if let _ = readLine(),
let cardBasket = readLine()?.split(separator: " ").compactMap({ Int($0) }),
let _ = readLine(),
let hands = readLine()?.split(separator: " ").compactMap({ Int($0) }) {
var result = ""
var countAbout = [Int: Int]()
for card in cardBasket {
if let count = countAbout[card] {
countAbout[card] = count + 1
} else {
countAbout[card] = 1
}
}
for card in hands {
if let count = countAbout[card] {
result += "\(count) "
} else {
result += "0 "
}
}
print(result)
}이랬는데 시간초과가 나오더라구요
일단 메소드들의 시간복잡도를 보니까 그나마 문제가 되는게 compactMap인 거 같았습니다
copmactMap의 시간복잡도가 재료의 count + 결과의 카운트인 O(n+m)이더라구요
얘를 고친게 두번째 버전인데
두번째 버전
if let _ = readLine(),
let cardBasket = readLine()?.split(separator: " ").map({ Int($0)! }),
let _ = readLine(),
let hands = readLine()?.split(separator: " ").map({ Int($0)! }) {
var result = ""
var countAbout = [Int: Int]()
for card in cardBasket {
if let count = countAbout[card] {
countAbout[card] = count + 1
} else {
countAbout[card] = 1
}
}
for card in hands {
if let count = countAbout[card] {
result += "\(count) "
} else {
result += "0 "
}
}
print(result)
}얘가 정말 문제인게 맞나 싶어서 강제로 언랩핑을 했는데 똑같이 시간초과가 됐습니다
딕셔너리를 쓴 게 문제인 건가 싶어서 얕게 조사를 해보았는데 딕셔너리는 해시테이블을 사용하고 있고, 때문에 값에 접근하거나 수정하는 부분이 O(1) 이더라구요
여기서 이제 또 입출력 속도 문제인가 싶어서 남들도 그렇게 풀었나 궁금해서 검색을 해봤는데
통과가 되는 코드
let n = Int(readLine()!)!
var nArr = readLine()!.split(separator: " ").map{Int(String($0))!}
let m = Int(readLine()!)
let mArr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dict = [Int: Int]()
var result: [Int] = []
nArr.sort()
for i in nArr{
if dict.keys.contains(i) {
dict[i]! += 1
}else {
dict[i] = 1
}
}
for j in mArr{
if dict.keys.contains(j) {
result.append(dict[j]!)
}else {
result.append(0)
}
}
print(result.map{String($0)}.joined(separator: " "))
제꺼랑 크게 차이가 나지 않고 오히려 contains를 사용하는 측면에서 더 큰 시간복잡도를 가지고 있다고 생각되는데...
제가 뭘 놓치고 있는 건지 잘 모르겠습니다 ㅋㅋ
도움이 필요합니다!
첫번째 버전
이랬는데 시간초과가 나오더라구요
일단 메소드들의 시간복잡도를 보니까 그나마 문제가 되는게 compactMap인 거 같았습니다
copmactMap의 시간복잡도가 재료의 count + 결과의 카운트인 O(n+m)이더라구요
얘를 고친게 두번째 버전인데
두번째 버전
얘가 정말 문제인게 맞나 싶어서 강제로 언랩핑을 했는데 똑같이 시간초과가 됐습니다
딕셔너리를 쓴 게 문제인 건가 싶어서 얕게 조사를 해보았는데 딕셔너리는 해시테이블을 사용하고 있고, 때문에 값에 접근하거나 수정하는 부분이 O(1) 이더라구요
여기서 이제 또 입출력 속도 문제인가 싶어서 남들도 그렇게 풀었나 궁금해서 검색을 해봤는데
통과가 되는 코드
제꺼랑 크게 차이가 나지 않고 오히려 contains를 사용하는 측면에서 더 큰 시간복잡도를 가지고 있다고 생각되는데...
제가 뭘 놓치고 있는 건지 잘 모르겠습니다 ㅋㅋ
도움이 필요합니다!