[10816 - 숫자 카드 2] 시간 초과가 나네요

[soo941226]

첫번째 버전

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를 사용하는 측면에서 더 큰 시간복잡도를 가지고 있다고 생각되는데...

제가 뭘 놓치고 있는 건지 잘 모르겠습니다 ㅋㅋ

도움이 필요합니다!

[ictechgy]

Fast I/O 문제인 것 같네요!

[soo941226]

감사합니다 코든! 입출력 속도를 개선함으로써 통과는 되었습니다!

그래도 근본적인 문제는 해결이 되지 않은 것 같아서 고민을 조금 해보았는데, 제가 갖고 있는 짐작은 통과가 되는 코드들은 옵셔널을 강제로 언랩핑을 시켜놓는 반면, 저는 옵셔널을 그대로 사용을 한 뒤 if let을 통해서 연관값을 꺼내고 있는데

Optional.some(let associatedValue)

에서 Optional의 인스턴스를 메모리에 할당하고, 이에 접근하고, 그 뒤에 연관값을 꺼내고, 새로운 메모리를 할당하고 다시 접근하고... 이러한 과정이 오버헤드가 큰 작업이 아닌가 하는 생각을 갖게 되었습니다. 그래서 시간초과가 나지 않았나... 짐작을 하게 되었는데 확인을 어떻게 해야할지 모르겠네요 ㅋㅋ 어렵네요...

[soo941226]

문제는 일단 통과가 되었으므로 이슈는 닫겟습니다! 도와주셔서 감사합니다 코든~!