[백준] 21921번 : 블로그

블로그

---

풀이 방법

문제를 읽고, 컴퓨터 구조 시간에 배운 TCP 쪽에 윈도우가 생각났다.
무턱대고 2중 for문으로 구현했다가 아니나 다를까 시간초과 문제가 나버렸다..

틀린 로직

		int max = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<=n-x;i++) {
            int sum = 0;
            sum += visiters[i];
            for(int j=i+1;j<i+x;j++) {
                sum += visiters[j];
            }
            max = Math.max(max, sum);
            if(max==sum)
                map.put(max, map.getOrDefault(max,0)+1);
        }

여기서 처음을 시작으로 잡고, x 범위만큼의 값을 더하면서 최대값인지 아닌지 확인해주는 로직이였다.
이제보니 시간초과가 날 수 밖에 없는 로직이였다.

다른 블로그를 찾아보니 슬라이딩 윈도우 라는 알고리즘이 존재했다.
로직자체는 매우 쉽다.
첫 시작 윈도우를 0~x 까지의 값들의 합으로 설정하고,
윈도우를 이동시켜주면서 값을 비교하면 되는 문제였다.

		// 첫 윈도우 설정
        int sum = 0;
        for(int i=0;i<x;i++)
            sum += visitors[i];

        int max = sum;
        int cnt = 1;
        for(int i=0;i<n-x;i++) {
            // 윈도우 이동
            sum += visitors[i+x];
            sum -= visitors[i];

            if(sum == max) {
                cnt++;
            }

            if(sum > max){
                cnt = 1;
                max = sum;
            }

        }

해당 알고리즘을 알고 있었다면 10분 안에 풀고 넘길 문제였지만, 나로써는 시간을 잡아먹었던 것 같다..

현재 목표로는 문제를 확인하고 10분안에 어떤 자료구조로 어떤 알고리즘을 해결할지 판단하기!

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 cnt = 1;
        for(int i=0;i<n-x;i++) {
            // 윈도우 이동
            sum += visitors[i+x];
            sum -= visitors[i];

            if(sum == max) {
                cnt++;
            }

            if(sum > max){
                cnt = 1;
                max = sum;
            }

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