글 읽기 - 9020 swift 시간초과

santoo 3년 전 0

어떻게 해결하면 좋을까요? 어느 부분이 시간복잡도가 큰지 궁금합니다.

import Foundation
for _ in 1 ... Int(readLine()!)! {
    let line = Int(readLine()!)!
    var sosu: [Int] = []
    var count = 0
    let total = Array<Int>(2 ... line)
    for i in total {
        for j in 1 ... Int(sqrt(Double(i))) {
            if i % j == 0 {
                count += 1
            }
        }
        if count == 1 {
            sosu.append(i)
        }
        count = 0
    }
    let a = sosu.filter { $0 <= line / 2 }
    let b = sosu.filter {$0 >= line / 2}
    for i in a.sorted(by: >) {
        let j = line - i
        if b.contains(j) {
            print(i)
            print(j)
            break
        }
    }
}

nahwasa 3년 전 0

소수를 입력받을 때 마다 새로 찾아줄 필요가 있을까요?

10000까지가 손해라, line 크기에 맞게 소수를 계산하시려던 것 같으나,

tc 10에 전부 10000짜리 이런거면 어쩌시려구요!

그냥 미리 10000까지 배열에 소수 구하시고 입력받으시는게 낫습니다.

santoo 3년 전 0

아... 감사합니다. 더 효율적으로 하려다가 되려 비효율적으로 되버렸군요. 감사합니다! 덕분에 한 수 배워갑니다 ㅎㅎ 해당 문제 해결했어요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9020 swift 시간초과

santoo 3년 전 0

nahwasa 3년 전 0

santoo 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말