[Swift] 백준 21921 - 블로그

문제

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

21921번: 블로그

 

시간초과 풀이 1 (투포인터 사용)

import Foundation

let input = readLine()!.split(separator:" ").map { Int(String($0))! }
let n = input[0], x = input[1]
let arr = readLine()!.split(separator:" ").map { Int(String($0))! }

var start = 0
var end = x-1
var sum = 0
var answer = 0
var count = 0 //처음에는 max값을 초기화해야하므로 카운트하지 않아서 -1

var temp:[Int] = []

while end < n {
  for i in start...end {
    sum += arr[i]
  }
  temp.append(sum)

  if answer < sum {
    answer = sum
  }
  
  sum = 0
  
  start += 1
  end += 1
}

if answer == 0 {
  print("SAD")
} else {
  print(answer)
  print(temp.filter { $0 == answer }.count)
}

- 처음에는 투포인터로 풀고싶어서 start와 end 지점을 같이 움직이면서 일일이 구간합을 구해서 최대값을 구하는 방식으로 했더니 시간초과가 났다. 아무래도 n의 범위가 25000이다보니 while 문 안에 for문이 한번 더 있어서 O(N^2)이므로 시간초과가 난 듯 하다.

 

통과한 풀이 (구간합 빠르게 구하기)

 

import Foundation

let input = readLine()!.split(separator:" ").map { Int(String($0))! }
let n = input[0], x = input[1]
let arr = readLine()!.split(separator:" ").map { Int(String($0))! }

var sum = 0
var prefix_sum = [0]

for i in arr {
  sum += i
  prefix_sum.append(sum)
}

var start = 0
var temp:[Int] = []

while start+x <= n {
  temp.append(prefix_sum[start+x]-prefix_sum[start])
  start += 1
}

let max_val = temp.max()!

if max_val == 0 {
  print("SAD")
} else {
  print(max_val)
  print(temp.filter { $0 == max_val }.count)
}

- 구간합 빠르게 구하기 알고리즘을 사용하면 prefix_sum 배열에는 각 인덱스에 그 인덱스까지의 누적합이 들어있다. 잘 설명되어있는 링크

- 그리고 구간 간격이 x일이므로, start+x번째 누적합에서 start번째 누적합을 빼면 start와 start+x 지점 간의 구간 합이 된다.

ex) 예제 1

5 2
1 4 2 5 1

여기서 prefix_sum은 [0, 1, 5, 7, 12, 13] 이렇게 인데 1일부터 2일, 즉 2일간의 방문자 수는 prefix_sum[2] - prefix_sum[0]과 같다.

- 여기서 temp라는 인덱스에 각 구간합을 append 했고, max값을 가진 원소의 갯수를 출력했다. (temp.filter { $0 == max_value }.count)

- 구간합 빠르게 구하기 알고리즘은 시간복잡도가 O(N) 이므로 위 시간초과 코드보다 더 빠르게 실행할 수 있다.