[Swift 알고리즘] 백준 10025 게으른 백곰

×

슬라이딩 윈도우, 투 포인터, 누적 합 Silver 3

백준 10025 게으른 백곰

기본적인 슬라이딩 윈도우 문제로, 로직이 어렵진 않았는데 자나 깨나 조건 주의...!

 

답안 

// 76920KB 156ms
let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
var ice: [Int] = Array(repeating: 0, count: 1000001)
var start = 0, end = 2 * nk[1]
var sum = 0

for _ in 0..<nk[0] {
    let gx = readLine()!.split(separator: " ").compactMap { Int($0) }
    ice[gx[1]] = gx[0]
    if gx[1] <= end { sum += gx[0] }
}

var maxSum = sum
while end < 1000000 {
    end += 1
    sum -= ice[start]
    sum += ice[end]
    maxSum = max(maxSum, sum)
    start += 1
}

print(maxSum)

 

양동이가 있는 x 좌표의 범위는 0 ~ 100만 까지인데,

백곰이 움직일 수 있는 거리 K 의 범위는 400만인 것에 주의..!

* 범위가 100만일 경우, 배열에 100만개의 메모리를 할당하고 O(n)으로 100만번 반복문을 돌리는 것은 전혀 문제가 되지 않으니 너무 복잡하게 생각하지말자..! 가장 쉬운 해결법이 가장 효율적인 답안일수도!?!?

 

풀이

let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = nk[0]           // 양동이 수
let k = nk[1]           // 최대 합 길이
var ice: [Int] = Array(repeating: 0, count: 1000001)
var sum = 0

for _ in 0..<n {
    let gx = readLine()!.split(separator: " ").compactMap { Int($0) }
    let index = gx[1]   // 양동이 x 좌표
    let value = gx[0]   // 얼음의 수
    ice[index] = value
    if index <= k * 2 { sum += value } // 최소 거리 내 얼음들의 합 구하기
}

// 얼음들의 합 최대 값 구하기
var maxSum = sum
var start = 0, end = k * 2
while end < 1000000 {
    end += 1
    sum -= ice[start]
    sum += ice[end]
    maxSum = max(maxSum, sum)
    start += 1
}

print(maxSum)

 

 

<내가 저지른 실수 모음>

야레야레..

괜히 복잡하게 머리쓴다고 굳이 불필요한 메모리를 낭비하지 말고 필요한 값들만 딕셔너리에 저장하고,

x 좌표의 최소값 ~ 최대값 사이에서만 최대 구간합을 구하려고 했는데

시간은 더 오래 걸리고 생각만큼 메모리가 절약되는 방법은 아니라 비추비추 🤢

+ 딕셔너리라 망정이지 구간 합 구할 때 s...min(e, maxX) 안해주고 s...e 해주면 배열에서는 무려 index 에러까지 날 수 있다눙

// 75316KB 224ms
let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
let k = 2 * nk[1]       // 최대 합 길이
var dict = [Int: Int]() // [x 좌표: 얼음 개수]
var minX = 1000000, maxX = 0  // x 좌표 최소값, 최대값

for _ in 0..<nk[0] {
    let gx = readLine()!.split(separator: " ").compactMap { Int($0) }
    dict.updateValue(gx[0], forKey: gx[1])
    minX = min(gx[1], minX)
    maxX = max(gx[1], maxX)
}
// 구간 합 구하기
var sum = 0
var s = minX, e = minX + k
for i in s...min(e, maxX) {
    if let x = dict[i] {
        sum += x
    }
}
// 최대 구간 합 구하기
var maxSum = sum
while e < maxX {
    e += 1
    sum -= dict[s] ?? 0
    sum += dict[e] ?? 0
    maxSum = max(maxSum, sum)
    s += 1
}

print(maxSum)

 

다음과 같이 반복문을 설정해줘도 에러 나거나 틀린 답이 나오니깐 조건에 주의할 것

while end <= 1000000 {
    end += 1
    sum -= ice[start]
    sum += ice[end]
    maxSum = max(maxSum, sum)
    start += 1
}

while end < 1000000 {
    sum -= ice[start]
    sum += ice[end]
    maxSum = max(maxSum, sum)
    start += 1
    end += 1
}

 

 

오랜만에 푸니까 뇌가 안돌아간다,, 반성하자 ㅎ