[Algorithm] 백준 - 15824번 너 봄에는 캡사이신이 맛있단다 (Swift)

문제 소개

해결 과정

첫 번째 풀이 (50점)

최대, 최솟값을 결정하고 나머지는 2^n으로 최대 최소일 경우 몇 번의 경우가 있는지를 구하면 되는 문제였다. 문제는 모듈러 연산... 처음에 2의 n제곱을 구하는데 모듈러 연산을 안 해줘서 자꾸 런타임 오류가 났었다. 

let fileIO = FileIO()

let n = fileIO.readInt()
let mod = 1_000_000_007

var answer = 0
var sco = [Int]()

for _ in 0..<n {
    let s = fileIO.readInt()
    sco.append(s)
}

sco.sort()

var pow2 = [Int](repeating: 1, count: n)
for i in 1..<n {
    pow2[i] = (pow2[i - 1] * 2) % mod
}

for i in 0..<n {
    for j in (i + 1)..<n {
        let scobil = sco[j] - sco[i]
        answer = (answer + scobil * pow2[j - i - 1] % mod) % mod
    }
}

print(answer)

하지만 이 풀이의 문제점은 2중 반복문이 들어가기 때문에 n = 300,000 일때 90000,000,000의 연산을 하기 때문에 시간초과가 발생한다.

정답 (250점)

생각해보면 단순했다. 굳이 최대 최소를 결정할 필요 없이 하나의 메뉴가 있다면 최대일 경우는 그것보다 전에 있는 메뉴 개수의 2^n이고, 그 메뉴가 최소일 경우는 그 이후에 있는 메뉴 개수의 2^n이다.

let n = Int(readLine()!)!

let mod = 1_000_000_007
var answer = 0

var menus = readLine()!.components(separatedBy: " ").map { Int($0)! }
menus.sort()

var pow2 = [Int](repeating: 1, count: 30_0001)
for i in 1..<300000 {
    pow2[i] = (pow2[i - 1] * 2) % mod
}

for i in 0..<n {
    let menu = menus[i] % mod
    var cases = (pow2[i] - pow2[n - i - 1]) % mod
    if cases < 0 { cases += mod }
    answer = (answer + menu * cases % mod) % mod
}

print(answer)

입출력 라이브러리를 쓰지 않으면 564ms, 쓰면 80ms 나오는 듯하다.