[백준(BOJ)] 21921 블로그 - 스위프트(Swift)

[Silver III] 블로그 - 21921

문제 링크

성능 요약

메모리: 84696 KB, 시간: 92 ms

분류

누적 합, 슬라이딩 윈도우

문제 설명

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

풀이

슬라이딩 윈도우라는 알고리즘 방법을 사용하면 됩니다. 

 

슬라이딩 윈도우란 고정된 크기의 배열을 탐색할 때 사용되며, 조건에 따라 양 끝 값을 더하고 빼주면서 배열을 조정합니다.

 

따라서 해당 크기만큼의 배열의 합을 지정한 뒤, 차례대로 left, right를 이동시키면서 만약 현재 최대값과 같다면 1을 더해주고, 
만약 현재 최대값보다 크다면 해당 값을 최대값으로 지정하고 정답을 1로 초기화해줍니다.

 

풀이 방법

 

다음은 코드입니다.

let nx = readLine()!.split(separator: " ").map { Int($0)! }
let (n, x) = (nx[0], nx[1])
let visit = readLine()!.split(separator: " ").map { Int($0)! }
var (left, right, sum, max, ans) = (0, x - 1, 0, 0, 1)

for i in 0..<n - x + 1 {
    if i == 0 { // 처음 값
        for j in 0..<x {
            sum += visit[j]
        }
        max = sum
    }
    
    else {  // 처음 이후
        sum = sum - visit[i - 1] + visit[i + x - 1] // 첫 번째 값 빼주고, 마지막 값 더하기
        if sum == max {
            ans += 1
        } else if sum > max {
            max = sum
            ans = 1
        }
    }
}

if max == 0 {
    print("SAD")
} else {
    print(max)
    print(ans)
}