자바 기초 알고리즘 - SWEA 영어공부 이분탐색

자바로 처음으로 이분탐색을 구현해보았는데, 파이썬이랑 사실상 다를게 없어서 가볍게 구현할 수 있는 문제.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS 

SW Expert Academy

 

인덱스를 선택하고 거기서 오른쪽으로 최장 몇칸 갈 수 있는지를 체크한다.

 

왼쪽은 고려하지 않아도 되는게, 왼쪽 인덱스에 바로 붙어있어 연속되는 수강일이 있다고 하더라도, 이미 왼쪽에서 처리해주면서 넘어왔기 때문에 왼쪽은 볼 필요가 없다.

 

1. 반복문으로 모든 수강일를 돌기

 

2. 오른쪽 인덱스로 하나 늘어날 때마다 수강한 날이 하나 늘어남

 

3. 오른쪽 인덱스 - 선택한 인덱스 + 1 = 수강한 날의 일 수, 오른쪽 값 - 선택한 값 + 1 = 전체 일 수

 

4. 전체 일 수 - 수강한 날 수 = 해킹해서 채워야 하는 날 수

 

5. 정답의 최솟값은 각각의 수강 날짜가 너무 범위가 커서 수강 날짜를 이을 수 없어, 하나의 날짜에 p로 덧붙이는 경우

ex) 4 420 (수강한 날은 2일이지만, 전체 일수는 417일, 그러므로 하나만 고르고 p로 이어붙이는 1+p가 최솟값)

 

6. 오른쪽 인덱스를 정하고 나면 해당 인덱스까지 연속으로 잇기 위해 필요한 날짜만큼 p에서 빼고, 남은 p값은 추가로 더해주기 == 해당 기간동안 수강한 날수 + p

 

import java.util.*;
import java.io.*;
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t = 1; t<= T; t++){
            int n = sc.nextInt();
            int p = sc.nextInt();
            int[] lst = new int[n];
            for(int i=0; i<n; i++){
                lst[i] = sc.nextInt();
            }
            int answer = 1 + p;
            for(int i=0; i<n-1; i++){
                int start = i+1;
                int end = n-1;
                int res = i;


                while(start <= end){
                    int mid = (start + end)/2;
                    int totalDay = lst[mid] - lst[i] + 1;
                    int attendDay = mid - i + 1;
                    if(totalDay - attendDay <= p){
                        start = mid + 1;
                        res = mid;
                    }else{
                        end = mid - 1;
                    }
                }
                int totalDay = lst[res] - lst[i] + 1;
                int attendDay = res - i + 1;
                answer = Math.max(answer, p - (totalDay - attendDay) + totalDay);

            }
            System.out.println("#"+t+" "+answer);
        }

    }
}