[SWEA] 10507 영어공부 JAVA

문제링크

SW Expert Academy

 

1. 문제의 유형 및 이해

이분탐색(parametric Search) , TwoPointer

영어 공부 랭킹 시스템에 따르면, 가장 길게 공부할 수록 랭킹이 높아진다고 한다.

수림이는 영어보다 해킹을 좋아한다. 그래서 수림이가 영어공부한 실제 공부한날이 주어지고

p개의 날을 적절히 해킹하여 체크하였을 때 랭킹을 가장 높일 수 있도록 가장 길게 공부한날을 만들어보자.

 

0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 과 같은 수열에서

X개를 1로 바꿀 수 있을 때 연속하는 1의 최대 개수는? 이라고 묻는 문제와 같다.

 

문제에서의 조건이 $1<= $ 공부한날, 체크할 수 있는 날 $<= 200000)이다.

또한 영어 공부를 실제로한 날은 번호로 주어지고 번호는 0~$10^6$이라고 한다.

2. 문제 접근 방법

가장 쉽게 생각하기

쉽게 생각하면 공부한날 부터 체크할 수 있는 날 만큼 체크를 쭉 해보면 된다.

체크를 하면서 가장 길게 갔던 날을 체크하면 날을 구할 수 있다.

그렇게 되면 공부한날(N) 부터 체크할 수 있는 날만큼(P) 쭉 체크를 한다 치면 최악의 경우
O(NP) 만큼의 시간 복잡도를 가지게 된다. 최악의 경우 O($N^2$)가 된다.

 

조금 더 나아가보자,

1. 날짜는 주어진 날의 값 차이를 통해 빠르게 계산할 수 있다.

2. a 날짜에서 최대로 간 날짜가 x라고 하면 

   a다음 날짜 b에서는 무조건 x로 갈 수 있다. 즉, 다시 계산하는 것이 아니라,

   x부터 다시 확인하면 된다. 즉, O(N)에 확인이 가능하다.

left = 공부를 한 시작 날짜   

right = 공부를 한 마지막 날짜

라고 했을 때 left~right만큼 공부하고, 이를 채우는데 사용한 날짜를 제외한 나머지 날짜를 뒤에다 붙여주면 최대로 만들 수 있는 길이가 된다.

시작날짜에서 갈 수 있는 최대한의 마지막 날짜를 구하여 left와 right 두개의 포인터만 움직이며 구현해보자.

 

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

public class Main {
    static int N, P;
    static int[] day;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tt = 1; tt <= T; tt++) {
            sb.append('#').append(tt).append(' ');
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            P = Integer.parseInt(st.nextToken());
            day = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) day[i] = Integer.parseInt(st.nextToken());

            int ans = findByTwoPointer();
            sb.append(ans).append('\n');
        }
        System.out.println(sb.toString());
    }

    public static int findByTwoPointer() {
        int ans = 0;
        int right = 0;
        for (int left = 0; left < N; left++) {
            int diffDay = 0;
            //공부 시작한 날로부터 최대한 가본다.
            while (right < N) {
                diffDay = (day[right] - day[left] + 1) - (right - left + 1);
                //다만 사이에 체크한 값이 주어진 P보다 작거나 같아야한다.
                if (diffDay <= P) right++;
                else
                    break;
            }
            right--;
            diffDay = (day[right] - day[left] + 1) - (right - left + 1);
            
            //거리 계산 (공부한 마지막 날짜 - 시작한날짜 + 남아있는 체크 횟수)
            ans = Math.max(ans, day[right] - day[left] + 1 + P - diffDay);
        }
        return ans;
    }
}

 

조금 다르게 생각해보자.

우리가 찾고자 하는 건, 시작날짜 A로 부터 P만큼 갈 수 있는 어떠한 날짜이다.위해서 구한 것 처럼 우리는 P이하로 체크하여 갈 수 있는 마지막 공부날짜를 찾아 날짜를 계산하였다."P 이하로 체크하여 갈 수 있는 마지막 공부날짜를 찾아" 를 빠르게 탐색하기 위해 이분탐색으로 찾아보자.

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

public class Solution {
    static int N, P;
    static int[] day;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tt = 1; tt <= T; tt++) {
            sb.append('#').append(tt).append(' ');
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            P = Integer.parseInt(st.nextToken());
            day = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) day[i] = Integer.parseInt(st.nextToken());

            int ans = 0;
            for(int i =0;i<N;i++){
                ans = Math.max(ans, findByBinarySearch(i));
            }
    
            sb.append(ans).append('\n');
        }
        System.out.println(sb.toString());
    }


    public static int findByBinarySearch(int index) {
        int left = index;
        int right = N - 1;
        int ans = 0;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int diffDay = (day[mid] - day[index] + 1) - (mid - index + 1);
            if (diffDay <= P) {
                ans = Math.max(ans, (day[mid] - day[index] + 1) + (P - diffDay));
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}