백준 3020번 개똥벌레 Swift

https://www.acmicpc.net/problem/3020

 

 

내 코드

let input = readLine()!.split(separator: " ").map { Int($0)! }
let N = input[0]
let H = input[1]

var list = Array(repeating: 0, count: H)

// O(N)
for i in 0..<N {
    let wall = Int(readLine()!)!
    if i % 2 == 0 { // 짝수번째 일때
        list[0] += 1
        list[wall] -= 1
    } else { // 홀수번째 일때
        list[H-wall] += 1
    }
}
var result: [Int] = []

// O(N)
for i in 1..<list.count {
    list[i] = list[i] + list[i-1]
}

let minValue = list.min()!
let minCount = list.filter { $0 == minValue }.count
print(minValue, minCount)

 

Review

이 문제는, N의 크기가 200,000 이므로 시간 복잡도가 O(N^2)이 넘어가면 시간 초과가 뜨게 됩니다.

Imos method 이라는 유명한 문제인데, 누적합을 활용하여 풀었습니다.

이모스법을 요약하면

1. 벽의 시작(아래)과 끝(위)에 1과 -1을 써줍니다.

 

2. 해당 숫자들을 높이별로 다 더해줍니다. [3. -1, 1, -1, 1, -1, 1]

 

3. 더해준 숫자들을 아래서부터 누적합을 해줍니다. [3, 2, 3, 2, 3, 2, 3]

 

4. 누적합 리스트에서 최솟값과, 최솟값의 개수를 세어주면 문제에서 제시되는 장애물의 최솟값과 구간의 수를 쉽게 구할 수 있습니다.
[3, 2, 3, 2, 3, 2, 3]