[SWEA] 10507. 영어 공부

문제

---

1. 공부한 날들의 차이를 기록했다. 그 차이들의 연속된 합이 p 보다 작을 때 최대 몇 개를 더할 수 있는 지가 답이라고 생각했다. 하지만 시간복잡도가 n^2 이기 때문에 시간 초과가 일어났다.

2. left, right 를 놓고, p 만큼 r을 전진시킨다. 만약 공부한 날이라면 p를 줄이지 않고 움직일 수 있다. p == 0 일 때 l을 전진시키고 공부한 날이 아니라면 p++ 를 해준다. r 이 끝에 도착했을 때 끝나게된다.

실수

---

시간 제한이 있는 경우 시간 복잡도를 생각해보자

코드

---

1. 첫 번째

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Solution {
    static StringBuilder result = new StringBuilder();

    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        int n;
        //////////////////////////
        int[] blankDays = new int[200000];
        int p, max, left, cnt, d1, d2;
        ///////////////////////////
        for (int test_case = 1; test_case <= T; test_case++) {
            result.append("#" + test_case + " ");
            st = new StringTokenizer(br.readLine());
            n = Integer.parseUnsignedInt(st.nextToken());
            /////////////////////////////
            p = Integer.parseUnsignedInt(st.nextToken());

            st = new StringTokenizer(br.readLine());

            d2 = Integer.parseUnsignedInt(st.nextToken());
            for (int i = 0; i < n - 1; i++) {
                d1 = d2;
                d2 = Integer.parseUnsignedInt(st.nextToken());

                blankDays[i] = d2 - d1 - 1;
            }

                        max = 0;
            for (int i = 0; i < n - 1; i++) {
                left = p;
                cnt = -1;
                while (left >= 0  && (i + cnt) < n - 1) {
                    cnt++;
                    left -= blankDays[i + cnt];
                }
                max = Math.max(max, cnt);
                if (i + max >= n) {
                    break;
                }
            }

                    result.append(max + p + 1 + "\n");
            System.out.print(result);
            result.setLength(0);
        }
    }
}

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Solution {
    static StringBuilder result = new StringBuilder();

    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        int n;
        //////////////////////////
        int p, max, left, right, cnt, lastday;
        ///////////////////////////
        for (int test_case = 1; test_case <= T; test_case++) {
            boolean[] days = new boolean[1000001];

            result.append("#" + test_case + " ");
            st = new StringTokenizer(br.readLine());
            n = Integer.parseUnsignedInt(st.nextToken());
            /////////////////////////////
            p = Integer.parseUnsignedInt(st.nextToken());

            lastday = 0;
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                lastday = Integer.parseUnsignedInt(st.nextToken());
                days[lastday] = true;

            }

            left = right = 1;
            cnt = 0;
            max = p + 1;
            while (right < lastday + 1) {
                if (days[right]) {
                    cnt++;
                    right++;
                    max = Math.max(max, cnt);
                } else {
                    if (p == 0) {
                        max = Math.max(max, cnt);
                        if (!days[left])
                            p++;
                        left++;
                        cnt--;
                    } else {
                        p--;
                        cnt++;
                        right++;
                    }
                }
            }

            result.append(max + "\n");
            System.out.print(result);
            result.setLength(0);
        }
    }
}