백준 21921번: 블로그 [JAVA]

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

21921번: 블로그

 

[틀린 코드]

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        int[] visitors = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            visitors[i] = Integer.parseInt(st.nextToken());
        }


        int max = 0;
        int answer = 0;
        for (int i = 0; i <= N - X; i++) {
            int tmp = 0;
            for (int j = i; j < i + X; j++) { // X기간동안의 방문자 수의 합
                tmp += visitors[j];
            }
            if (tmp > max) { // X기간동안 최고 방문자수가 갱신될 경우
                answer = 0;
                max = Math.max(tmp, max);
            }
            if (tmp == max) { // 최고방문자수가 max 와 같은 기간 카운팅
                answer++;
            }
        }
        System.out.println(max);
        System.out.println(answer);
    }
}

 

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        int[] visitors = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            visitors[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;
        for (int i = 0; i < X; i++) {
            sum += visitors[i];
        }


        int max = sum;
        int answer = 1;
        for (int i = 0; i < N - X; i++) { // 슬라이딩 윈도우

            //한칸 씩 이동
            sum += visitors[i+X];
            sum -= visitors[i];

            if (sum == max) { // 최다 방문자수가 유지될 경우 answer++
                answer++;
            }

            if (sum > max) { // 최다 방문자수가 갱신되었을 경우
                answer = 1;
                max = sum;
            }

        }
        if (max == 0) { // 최대 방문자 수가 0이라면 SAD 출력
            System.out.println("SAD");
        } else {
            System.out.println(max);
            System.out.println(answer);
        }
    }
}

 

[설명]

이 문제는 슬라이딩 윈도우 기법을 활용해야 한다. 처음에 이 문제를 풀었을때는 이중 for문으로 문제를 풀었었다. 그러자 시간초과 떴다. 그래서 2중for문을 해결하기 위해 for문을 하나로 두고 다시 풀었다.

먼저 입력을 받고 입력받은것중에 슬라이딩 윈도우로직을 사용할 구간만큼 미리 합을 구해놓는다.

그리고 for문을 이용해 한칸씩 이동해 나아가며 합을 계산한다. 

계산한 합이 알고있는 max값보다 클 경우 max값을 갱신하고 answer를 1로 초기화시킨다.

max값과 새로 이동해 계산한 합의 값이 같을 경우 answer를 1 증가시킨다.