[백준] 11663 선분 위의 점 - 이분탐색(BinarySearch) + LOWER BOUND + UPPER BOUND + 누적합(PrefixSum) + 메모리초과(OutOfMemory) JAVA

passionfruit200 2024. 8. 14. 10:48

2024. 8. 14. 10:48

https://www.acmicpc.net/problem/11663

코드설명

이분탐색(BinarySearch) 을 활용합니다.

처음에 먼저 떠올린 간단한 방법은 누적합(PrefixSum) + 메모리초과(OutOfMemory)입니다. 누적합을 활용하면 10^9 개의 메모리 공간이 필요해지면서 메모리 초과가 발생했습니다.

이분탐색을 활용하여, 하나의 숫자를 찾는데 logn 시간 내에 처리할 수 있습니다.

이 문제에서 가장 중요한점은,

1. left 값은 선분의 시작점입니다.

이 left값 보다 크거나 같은 첫번쨰 점을 찾아야 하므로lowerbound로 처리합니다. lowerbound는 주어진 값 이상인 첫번쨰 원소의 위치를 반환합니다.

2. right 값은 선분의 끝점입니다.

이 right 값보다 큰 첫번째 점을 찾아야 합니다.

문제 예시로보면 아래 예시에서 3 30 인 경우 3은 1, 30은 5 가 반환되어야 한다는 의미입니다.

따라서 upperbound를 사용하여, 주어진 값보다 큰 첫번쨰 원소의 위치를 반환합니다.

입력예시 1

5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8

디버깅

leftPos:0rightPos:3
leftPos:3rightPos:5
leftPos:1rightPos:5
leftPos:1rightPos:3
leftPos:2rightPos:2

3
2
4
2
0

따라서,

Lower Bound(left)는 선분에 포함되는 첫 번째 점의 인덱스를 반환합니다.
Upper Bound(right)는 선분에 포함되는 마지막 점의 다음 인덱스를 반환합니다.

그래서 Upper Bound(right) - Lower Bound(left)를 계산하면 선분에 포함되는 점의 개수를 정확히 구할 수 있습니다.

조금 더 쉽게 설명하면,

1. lower bound는 찾고자 하는 값 이상(즉, 같거나 큰값)이 처음 나타나는 위치입니다.

2. upper bound는 찾고자 하는 값보다 큰 값(즉, 반드시 큰 값, 만약 범위를 벗어난다면 다음 범위를 반환)이 처음으로 나타나는 위치입니다.

대부분의 이분탐색의 경우 lower bound를 사용한다고 생각하면 되겠습니다.

이 문제의 경우 구간을 구하는 문제이기에 upper bound를 사용했어야했구요.

코드

lowerbound와 upperbound를 활용하여 깔끔하게 풀 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache;
    private static int Q;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0;i<N; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        for(int i=0;i<M; i++) {
        	st = new StringTokenizer(br.readLine());
        	int left = Integer.parseInt(st.nextToken());
        	int right = Integer.parseInt(st.nextToken());
        	
        	int rightPos = binarySearchUpperBound(0, N-1, right);
        	int leftPos = binarySearchLowerBound(0, N-1, left);
        	
        		sb.append(rightPos - leftPos).append("\n");
        }
        System.out.println(sb);
        
    }
    
    private static int binarySearchLowerBound(int lo, int hi, int target) {
    	int left = lo - 1;
    	int right = hi + 1;
    	
    	while(left + 1 < right) {
    		int mid = (left + right) / 2;
    		
    		if(arr[mid] < target) {
    			left = mid;
    		}else if(arr[mid] >= target) {
    			right = mid;
    		}
    	}
    	return right;
    }
    
    private static int binarySearchUpperBound(int lo, int hi, int target) {
    	int left = lo - 1;
    	int right = hi + 1;
    	
    	while(left + 1 < right) {
    		int mid = (left + right) / 2;
    		
    		if(arr[mid] <= target) {
    			left = mid;
    		}else if(arr[mid] > target) {
    			right = mid;
    		}
    	}
    	return right;
    }
    
    
    
}

이분탐색으로 푼 코드입니다. 이 코드의 경우 upperbound와 lowerbound를 완전히 이해하고 풀지는 못했습니다.

그렇기 때문에, 출력 부분에 여러 제약조건을 처리함을 알 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache;
    private static int Q;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0;i<N; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        for(int i=0;i<M; i++) {
        	st = new StringTokenizer(br.readLine());
        	int left = Integer.parseInt(st.nextToken());
        	int right = Integer.parseInt(st.nextToken());
        	
        	int rightPos = binarySearch(0, N-1, right);
        	int leftPos = binarySearch(0, N-1, left);
        	
        	if(rightPos < N && arr[rightPos] == right) {
//        		System.out.println(rightPos - leftPos + 1);
        		sb.append(rightPos - leftPos + 1).append("\n");
        	}else {
//        		System.out.println(rightPos - leftPos);
        		sb.append(rightPos - leftPos).append("\n");
        	}
        }
        System.out.println(sb);
        
    }
    
    private static int binarySearch(int lo, int hi, int target) {
    	int left = lo - 1;
    	int right = hi + 1;
    	
    	while(left + 1 < right) {
    		int mid = (left + right) / 2;
    		
    		if(arr[mid] < target) {
    			left = mid;
    		}else if(arr[mid] >= target) {
    			right = mid;
    		}
    	}
    	return right;
    }
    
    
    
}

처음에 문제를 보고, 누적합으로 새로운 점이 생길떄마다 1씩 누적합시키는 방식으로 진행했습니다.

하지만, 좌표의 최대값이 1e9, 10억이기에 메모리초과가 발생합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache;
    private static int Q;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0;i<N; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] prefixSum = precalc();
        
        for(int i=0;i<M; i++) {
        	st = new StringTokenizer(br.readLine());
        	int left = Integer.parseInt(st.nextToken());
        	int right = Integer.parseInt(st.nextToken());
        	System.out.println(prefixSum[right] - prefixSum[left - 1]);
        }
        
        
        
    }
    
    private static int[] precalc() {
    	int[] prefixSum = new int[100];
    	
    	for(int i=0; i<N; i++) {
    		int start = arr[i]; 
    		int beforeSum = start == 0 ? 0 : prefixSum[start-1];
    		int next = i == N - 1 ? 100 : arr[i + 1];
    		for(int j=start; j<next; j++) {
    			prefixSum[j] = beforeSum + 1;
    		}
    	}
    	return prefixSum;
    	
    }
    
    
    
}

'알고리즘 > binary_search' 카테고리의 다른 글

[백준] 15810 풍선 공장 - 파라매트릭서치(Paramatric Search) JAVA (0)	2024.09.17
[백준] 13072 이상한 술집 - 파라매트릭 서치(ParamatricSearch) JAVA (0)	2024.09.05
[백준] 1166 선물 - 파라매트릭 서치(Paramatric Search) JAVA (0)	2024.08.13
[백준] 1515 수 이어 쓰기 - 파라매트릭 서치(Paramatric Search) + 부분 수열(SubSequence) JAVA (0)	2024.07.20
[백준] 2343 기타 레슨 - 파라매트릭 서치(Paramatric Search) JAVA (0)	2023.11.22

passionfruit200