백준 21921 블로그 | 실버 3

☁️ 문제 바로가기

나의 코드

package source_code;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class B_S3_21921_blog {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input = br.readLine().split(" ");
		int dayCnt = Integer.parseInt(input[0]);
		int duration = Integer.parseInt(input[1]);

		int[] visitCnt = new int[dayCnt];
		input = br.readLine().split(" ");

		for (int i = 0; i < dayCnt; i++) {
			visitCnt[i] = Integer.parseInt(input[i]);
		}

		// 초기 기간 sum 세팅
		List<Integer> visitInDuration = new ArrayList<>();
		int sum = 0;

		for (int i = 0; i < duration; i++) {
			sum += visitCnt[i];
		}

		visitInDuration.add(sum);

		// 뒷 기간도 마저 계산 후 리스트에 저장
		for (int i = 1; i <= (dayCnt - duration); i++) {
			sum -= visitCnt[i - 1];
			sum += visitCnt[i + duration - 1];

			visitInDuration.add(sum);
		}

		int max = Collections.max(visitInDuration);

		// max 값이 리스트에 몇 개인지 확인
		int sameNumCnt = 0;

		for (int i : visitInDuration) {
			if (i == max)
				sameNumCnt++;
		}

		StringBuilder sb = new StringBuilder();

		if (max == 0) {
			sb.append("SAD");
		} else {
			sb.append(max).append('\n');
			sb.append(sameNumCnt);
		}

		System.out.println(sb);
	}

}

우선 초기에 한 번만 기간 안의 방문자 수를 계산해서 list에 넣고, 이후에는 슬라이딩 윈도우 방식으로 계산해서 list에 넣었다.

초반에는 더 단순하게 했었는데,

package source_code;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class B_S3_21921_blog {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input = br.readLine().split(" ");
		int dayCnt = Integer.parseInt(input[0]);
		int duration = Integer.parseInt(input[1]);

		int[] visitCnt = new int[dayCnt];
		input = br.readLine().split(" ");

		for (int i = 0; i < dayCnt; i++) {
			visitCnt[i] = Integer.parseInt(input[i]);
		}

		// 기간 수만큼 sum 구해서 list에 저장
		List<Integer> visitInDuration = new ArrayList<>();

		for (int i = 0; i <= (dayCnt - duration); i++) {
			int sum = 0;

			for (int j = 0; j < duration; j++) {
				sum += visitCnt[i + j];
			}

			visitInDuration.add(sum);
		}

		int max = Collections.max(visitInDuration);

		// max 값이 리스트에 몇 개인지 확인
		int sameNumCnt = 0;

		for (int i : visitInDuration) {
			if (i == max)
				sameNumCnt++;
		}
		
		StringBuilder sb = new StringBuilder();

		if (max == 0) {
			sb.append("SAD");
		} else {
			sb.append(max).append('\n');
			sb.append(sameNumCnt);
		}
		
		System.out.println(sb);
	}

}

이건 슬라이딩 윈도우 방식이 아니라 직접 duration을 매번 새로 구해서 저장한 방식이다.
근데 이렇게 하면 시간초과! 가 발생해서 방법을 틀었다.

슬라이딩 윈도우

: 연속된 구간을 효율적으로 탐색할 때 쓰는 알고리즘 기법

핵심개념 고정된 크기의 창을 좌 -> 우로 이동시키며 탐색하는 방식
전체를 처음부터 끝까지 모두 계산하지 않고, 앞에서 계산한 결과를 재사용해서 시간 복잡도를 줄이는 게 핵심!

그래서 문제에서는 기간 동안 방문자 합을 구할 때, 처음 구한 sum 값에서 제일 앞의 값을 빼고, 새로운 제일 뒤의 값을 추가하는 방식으로 기존 sum을 재활용했다.

연속된 구간의 합, 최댓값 등을 계산할 때 이중 루프 대신 사용하면 좋은 개념이다.

투 포인터와 비교

항목	슬라이딩 윈도우	투 포인터
🔁 창 크기	고정	유동적
🎯 목적	일정 구간 합, 최댓값 등	조건을 만족하는 연속 구간 찾기
🔧 구조	보통 for 하나로 이동	start, end 두 포인터 함께 이동
🧠 예시	X일 합, K개 평균	부분합 ≤ S인 구간, 최소 길이 등

• 슬라이딩 윈도우: 정해진 길이의 구간을 효율적으로 탐색
• 투 포인터: 조건 만족하는 최적의 구간 길이 찾기

코드 리팩토링

• visitInDuration 리스트 제거
• max, count만 사용해서 비교하면서 바로 계산

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B_S3_21921_blog {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input = br.readLine().split(" ");
		int dayCnt = Integer.parseInt(input[0]);
		int duration = Integer.parseInt(input[1]);

		int[] visitCnt = new int[dayCnt];
		input = br.readLine().split(" ");
		for (int i = 0; i < dayCnt; i++) {
			visitCnt[i] = Integer.parseInt(input[i]);
		}

		int sum = 0;
		for (int i = 0; i < duration; i++) {
			sum += visitCnt[i];
		}

		int max = sum;
		int count = 1;

		for (int i = duration; i < dayCnt; i++) {
			sum = sum - visitCnt[i - duration] + visitCnt[i];

			if (sum > max) {
				max = sum;
				count = 1;
			} else if (sum == max) {
				count++;
			}
		}

		StringBuilder sb = new StringBuilder();
		if (max == 0) {
			sb.append("SAD");
		} else {
			sb.append(max).append('\n').append(count);
		}

		System.out.println(sb);
	}
}