[알고리즘]SWEA 9999: 광고 시간 정하기

 

주요 로직

영어 공부 문제(https://stonesy927.tistory.com/275)와 마찬가지로 ei < si+1 (1 ≤ i < N)로 광고 시간들이 정렬되어 있어 따로 정렬 로직은 필요하지 않다.

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

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

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

    if(ads[mid].end-ads[i].start<=L){
        left = mid+1;
    }else{
        right = mid - 1;
    }
}

영어 공부 문제에서는 numbers[mid]-numbers[i]-p<=mid-i

⇒ 연속 공부 기간보다 작거나 같은 idx 바로 다음 idx가 return되었다.

광고 시간 구하기 문제에서는 ads[mid].end-ads[i].start<=L

⇒ 광고 시작 ~ 끝까지 L보다 작거나 같은 idx 바로 다음 idx가 return될 것이다.

 

또한 누적합 개념을 사용하였다.

int ans = S[left]-S[i];
if(left<N) ans+=Math.max(0,(ads[i].start+L)-ads[left].start);

여기서 S[left]-S[i]는 i~left-1까지의 총 합이고, 마지막 left번째 광고에서 겹치는 부분이 있을 수 있기 때문에 더해주었다.

 

코드

최종적으로 이분 탐색을 이용하여 O(NlogN)으로 풀이하였다.

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

public class Solution {
    static int L, N;
    static Ad[] ads;
    static int[] S;

    static class Ad{
        int start;
        int end;

        public Ad() {}

        public Ad(int start, int end){
            this.start = start;
            this.end = end;
        }
    }

    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. 입력 및 초기화
            L = Integer.parseInt(br.readLine());
            N = Integer.parseInt(br.readLine());

            ads = new Ad[N];
            S = new int[N+1];
            for(int i=0; i<N; i++){
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                ads[i] = new Ad(s,e);

                //누적합
                S[i+1] = S[i]+e-s;
            }

            //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(ads[mid].end-ads[i].start<=L){
                        left = mid+1;
                    }else{
                        right = mid - 1;
                    }
                }

                int ans = S[left]-S[i];
                if(left<N) ans+=Math.max(0,(ads[i].start+L)-ads[left].start);

                answer = Math.max(answer, ans);
            }

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

 

 

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