코드트리 [자바 java] 가장 많이 겹치는 구간

https://www.codetree.ai/missions/8/problems/section-with-maximum-overlap?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 -1+1테크닉을 사용하는 문제이다. 

 

-1+1테크닉이란 

-1+1테크닉은 위와 같이 특정 위치에 겹치는 줄의 수를 알아내는데 유리한 알고리즘이다.

 

이를 브루트포스로 풀면, O(n)으로 직선마다 저 위치가 겹치는지 확인하는 과정이 필요하다.

하지만

 

이와 같이 직선의 가장 왼쪽 부분에는 +1을 하고 오른쪽 부분에는 -1을 하고, 0부터 k까지 계속 덧셈을 하면 직선 하나가 지나가면 +1과 -1이 더해지므로, 값에 영향을 미치지 않는다.(0이 더해지므로) 

 

이와 같은 방법으로 이 문제를 풀었다.

배열을 하나 만들고 주어진 선분의 앞 위치에 +1, 끝나는 위치에 -1을 한다. 그 다음 앞에서부터 차례로 더하기를 하고 이 값들 중 가장 큰 것을 출력한다.

 

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


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        int[] arr = new int[200001];

        int start;
        int end;

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());

            arr[start] += 1;
            arr[end] -= 1;

        }

        int max = 0;
        int sum = 0;

        for(int i = 0;i<200001 ; i++){
            sum += arr[i];
            max = Math.max(max, sum);

        }

        System.out.println(max);

    }
}