[알고리즘]SWEA 10507: 영어 공부

 

주요로직

n개의 수가 정렬되어 있어 정렬 로직 없이 이분탐색을 사용할 수 있다.

길이 n의 numbers 배열을 한번씩 순회하면서 + 이분탐색을 통해서 O(NlogN)으로 문제를 해결했다.

int answer = 0;
for(int i=0; i<n; i++){
    int left = i;
    int right = n-1;

    //.. 이분탐색 로직으로 특정 조건을 만족하는 경계값을 찾음
   
    answer = Math.max(answer, left-i+p);
}

이분탐색을 통해서 특정 조건을 만족하는 idx 바로 다음 값을 찾았다.

int left = i;
int right = n-1;

while(left<=right){
	int mid = (left+right)/2;
	
	if(numbers[mid]-numbers[i]-p<=mid-i){
		left = mid+1;
	}else{
		right = mid-1;
	}
}

그리고 연속으로 영어 공부를 할 수 있는 날 left-i+p을 계산하고, answer 값을 비교하며 최대값으로 update 해주었다.

answer = Math.max(answer, left-i+p);

 

코드

import java.io.*;
import java.util.*;

public class Solution_10507_binarySearch_영어공부 {
    static int n,p;
    static int[] numbers;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for(int test_case=1; test_case<=T; test_case++){
            //1. 입력 및 초기화
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            p = Integer.parseInt(st.nextToken());

            numbers = new int[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) numbers[i] = Integer.parseInt(st.nextToken());

            //2. 이분탐색
            int answer = 0;
            for(int i=0; i<n; i++){
                int left = i;
                int right = n-1;

                while(left<=right){
                    int mid = (left+right)/2;

                    if(numbers[mid]-numbers[i]-p<=mid-i){
                        left = mid+1;
                    }else{
                        right = mid-1;
                    }
                }

                answer = Math.max(answer, left-i+p);
            }

            System.out.printf("#%d %d%n", test_case, answer);
        }
    }
}

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