본문 바로가기
카테고리 없음

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

by 잔디🌿 2023. 8. 23.

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

     

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

    국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

    www.codetree.ai

     

    이 문제는 -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);
    
        }
    }