[백준] BOJ - 21921 블로그 자바 java (실버3)

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

21921번: 블로그

 

처음풀이(시간초과)

import java.util.*;
import java.io.*;
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[] arr=new int[n];
        List<Integer> list=new ArrayList<Integer>();//x일간 방문자수 저장을 위한 리스트
        
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        for(int i=0;i<=n-x; i++){
            int cnt=0;
            for(int j=i;j<i+x;j++){
                cnt+=arr[j];
            }
            list.add(cnt);
        }
        
        int maxVal=Collections.max(list);
        if(maxVal==0){
            bw.write("SAD");
        }else{
            bw.write(String.valueOf(maxVal)+"\n");
            bw.write(String.valueOf(Collections.frequency(list,maxVal))+"\n");
        }
        bw.flush();
        br.close();
        bw.close();
    }
}

 

성공한풀이

import java.util.*;
import java.io.*;
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[] arr=new int[n];
        
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        //첫번째 부분합
        long partSum=0; 
        for(int i=0;i<x;i++){
            partSum+=arr[i];
        }
        
        int cnt=1;
        long savedPartSum=partSum;
        for(int i=x; i<n; i++){
            partSum+=arr[i]-arr[i-x];
            
            if(savedPartSum==partSum){
                cnt++;
            }else if(partSum>savedPartSum){
                savedPartSum=partSum;
                cnt=1;
            }
        }
        
        if(savedPartSum==0){
            bw.write("SAD");
        }else{
            bw.write(savedPartSum+"\n"+cnt);
        }
        bw.flush();
        br.close();
        bw.close();
    }
}

 

Tip.

누적합 문제 :

일정 구간이 주어졌을때 최대 누적합과 개수를 구하기

- > 투포인터의 변형인 슬라이더를 이용하기

- > 반복문을 한번만 쓸수있게된다

 

참고한 블로그

https://ksb-dev.tistory.com/104

백준 - 21921 블로그(Java)