⚙️ 알고리즘/백준
[Swift] 백준 21921 - 블로그
dev_zoe
2023. 4. 25. 00:29
반응형
문제
https://www.acmicpc.net/problem/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) 이므로 위 시간초과 코드보다 더 빠르게 실행할 수 있다.
반응형