[Boj_21921] 블로그

📎 문제 링크

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

21921번: 블로그

 

▸ 문제

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

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

 

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

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

 

▸ 입력

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

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

 

▸ 출력

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

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

 

▸ 제한

•  1≤X≤N≤250,000
•  0≤ 방문자 수 ≤8,000

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 3
• 🔔  문제 유형 : 누적 합, 슬라이딩 윈도우
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

5 3
1 4 2 5 1

위의 예시로 풀이를 그려보면 아래와 같다.

(1)

1

4

2

5

1

1, 4, 2 구간, sum = 7

 

(2)

1

4

2

5

1

4, 2, 5 구간, sum = 11

 

(3)

1

4

2

5

1

2, 5, 1 구간, sum = 8

 

x칸만큼 주황색 부분을 옆으로 움직이므로 '슬라이딩 윈도우'를 사용하여 문제를 해결했다.

(1)에서의 합은 7이었고,

(2)와 같이 옆으로 한 칸 이동할 때는 빠지는 1을 빼주고 새로 들어오는 5를 더해주면 된다.

이 과정을 반복해 주면, 주황색 부분의 합 중 가장 큰 값이 x일 동안 가장 많이 들어온 방문자 수가 된다.

 

최대 방문자 수였던 기간은

현재 최대치(방문자 수) 보다 크다면 최대치를 갱신해 주고,

현재 최대치와 동일하다면 날짜를 카운팅 해주는 방식으로 구해주었다.

 

🔍 슬라이딩 윈도우란(Sliding window)?

• 윈도우(특정 범위)가 있을 때, 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘이다.
• 배열이나 리스트에서 요소의 일정 범위의 값을 비교할 때 사용하면 유용하다.
  • 구간 합 구하기, 부분 문자열 구하기 등에 활용 가능

 

🔍  슬라이딩 윈도우와 투 포인터

[ 공통점 ]

• 선형 배열(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우,
• O(N²) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다.

[ 차이점 ]

• 슬라이딩 윈도우는 구간의 길이를 고정적으로 잡기 때문에 포인터가 하나만 필요하다.
  • 즉, 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터가 하나만 있어도 부분 배열의 크기를 알고 있기 때문에 각 배열의 끝을 알 수 있다.
• 반면, 투 포인터는 구간의 길이를 가변적으로 잡기 때문에 구간의 양쪽 끝이 되는 포인터 두 개가 필요하다.

 

✔ 최종 코드

메모리 : 38940KB
시간 : 308ms

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 블로그를 시작하고 지난 일수
        int x = Integer.parseInt(st.nextToken()); // x일 동안

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) { // 1일차부터 n일차까지 하루 방문자 수 입력
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0; // 방문자수의 합
        int day = 1; // x일 동안 방문자가 가장 많이 들어온 기간
        for (int i = 0; i < x; i++) sum += arr[i]; // 1일부터 x일까지 방문자수의 합

        int max = sum; // 최대 방문자수
        for (int i = x; i < n; i++) {
            sum -= arr[i-x]; // 첫번째 제외
            sum += arr[i];

            if (max < sum) { // 최대 방문자수 갱신
                day = 0; // 기간 초기화 후 증가
                day++;
                max = sum;
            } else if (max == sum) { // 최대 방문자수가 같은 기간이면
                day++;
            }
        }

        if (max == 0) { // 최대 방문자 수가 0명
            bw.append("SAD" + "\n");
            bw.flush();
            return;
        }

        bw.append(max + "\n" + day);
        bw.flush();
        bw.close();
        br.close();
    }
}