[백준] Silver III. 블로그

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

 

 

사용 알고리즘

• 투 포인터

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    static int n, x; // n: 일 수, x: 구간
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        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());
        }

        int hi = 0;
        int res = arr[0];
        int max = Integer.MIN_VALUE;
        int count = 1;

        for(int lo = 0; lo < n; lo++) {
            while (hi < n && hi - lo + 1 < x) {
                hi++;
                if (hi != n) res += arr[hi];
            }

            if (hi - lo + 1 < x) break;

            if (res > max) count = 1;
            else if (res == max) count++;

            max = Math.max(max , res);
            res -= arr[lo];

        }

        if (max == 0) {
            System.out.println("SAD");
        }
        else {
            System.out.println(max);
            System.out.println(count);
        }
    }
}

 

 

회고

 

처음에 반례를 찾지 못해서 고민하다가, 질문 계시판에서 내 케이스에 딱 맞는 반례를 발견했다.

입력값
4 2
1 2 1 7

출력값
8 2

기대값
8 1

 

가장 많이 들어온 방문자 수 뿐만 아니라 기간도 같이 구해야 한다.

 

기존 코드에선 max를 갱신해주기 전에, res == max일 때만 count에 1을 더해주었다. 여기서 edge case는 저 예제에서도 찾아볼 수 있듯이, 최대값이 8이 아닌 3일때도 count를 업데이트 시켜주고 있다.

 

즉, res값이 max보다 크다는 뜻은 기존 값보다 더 큰 방문자 수를 찾았다는 뜻이므로 다시 1로 초기화 해줘야한다.

 

이외에는 정석적인 투포인터 문제였다.