블로그

[hsskey]

블로그

X일 동안 가장 많이 들어온 방문자 수와 기간들 출력

📝 제약조건

• 1 <= N <= 25 * 10^4

💡 예시

• Input: N = 5, X= 2 arr=[1, 4, 2, 5, 1]
  • Output: 7 1

문제 해결 과정

Step 1: 문제 이해하기

• 블로그 방문자 수를 기록한 배열에서 연속된 X일 동안 가장 많은 방문자 수와 해당 기간이 몇 번 있는지를 구하는 문제입니다.
• 제약조건:
  • 1 ≤ X ≤ N ≤ 250,000
  • 각 방문자 수는 0 이상 8,000 이하.
• 출력 조건:
  1. X일 동안의 최대 방문자 수를 출력합니다.
  2. 최대 방문자 수가 0인 경우 "SAD"를 출력합니다.
  3. 최대 방문자 수가 0이 아닌 경우 해당 기간의 개수를 출력합니다.
• 이 문제는 시간 복잡도 O(N)의 알고리즘으로 해결해야 합니다.

Step 2: 접근 방법

• 슬라이딩 윈도우 알고리즘:
  • 연속된 X일의 방문자 수 합을 효율적으로 계산하기 위해 슬라이딩 윈도우를 사용합니다.
  • 첫 X일 동안의 방문자 수 합을 초기 윈도우 합으로 설정합니다.
  • 그 후, 윈도우를 한 칸씩 오른쪽으로 이동시키면서 새로운 방문자 수를 추가하고, 윈도우에서 벗어나는 방문자 수를 빼주어 합을 갱신합니다.
  • 매번 갱신된 합을 통해 최대 합과 그 기간의 개수를 업데이트합니다.
  • 이 방법을 사용하면 O(N) 시간 복잡도로 문제를 해결할 수 있습니다.

Step 3: 코드 설계 (수도코드)

n, x, arr 입력받기

sum = 첫 X일 동안의 방문자 수 합
maxSum = sum
count = 1

left = 1
right = x

loop (right ≤ n):
    sum = sum + arr[right] - arr[left - 1]

    if sum == maxSum:
        count += 1
    if sum > maxSum:
        maxSum = sum
        count = 1

    left += 1
    right += 1

if maxSum == 0:
    "SAD" 출력
else:
    maxSum과 count 출력

Step 4: 코드 구현

• 설계한 알고리즘에 따라 코드를 작성하고 테스트합니다.

 const fs = require('fs')
 const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`
 const input = fs.readFileSync(filePath).toString().split('\n')

 const [n, x] = input[0].split(' ').map((item) => Number(item))
 const arr = [0, ...input[1].split(' ').map((item) => Number(item))]

 let sum = 0
 for (let i = 1; i <=n; i++) {
    if(i <= x) sum += arr[i]
 }

 let maxSum = sum // 가장 큰 합(첫번째 윈도우 구간에 대한 합계 설정)
 let count = 1 // 기간의 개수

 let left = 1
 let right = x

 while(true) { // 윈도우를 한 칸 오른쪽으로 이동하기
    left += 1
    right += 1

    if(right > n) break

    sum = sum + arr[right] - arr[left - 1] // 합을 계산하여 정답 갱신

    if(maxSum === sum) count += 1
    else if (maxSum < sum) { // 더 큰 합을 찾은 경우
        maxSum = sum
        count = 1
    }
 }
if(maxSum === 0) console.log('SAD')
else {
    console.log(maxSum)
    console.log(count)
}