BOJ) 선분 위의 점

선분 위의 점

11663번: 선분 위의 점

풀이

 

2달 전에 이 문제를 풀다가 계속 시간초과랑 오답이 번갈아 뜨면서 포기했던 문제였다.

오늘도 풀면서 3번이나 틀렸지만 결국 풀어냈다..!!

우선, 문제의 조건에 따라 각 점들은 int형으로 주어지고, 선분의 left, right 범위는 long 타입으로 주어진다.

 

그리고 완전탐색을 하게되면 가지치기를 엄청나게 잘하지 않는 이상은 시간초과가 뜬다고 생각했다.

그래서 binary search를 이용했다.

점들의 배열을 오름차순으로 정렬해두고 index를 탐색했다.

 

주어진 선분의 시작점 left보다 작은 곳에 있는 점들을 찾는 binary search와 right보다 큰 곳에 있는 점들을 찾는 binary search를 통해 각각 인덱스를 구한다.

(2번째 인덱스부터 left를 충족시키면 1번째 인덱스를 less에 저장하고, 5번째 인덱스까지 right를 충족시키면 6번 인덱스를 over에 저장하는 식으로)

 

그리고 less와 over는 각각 -1, size로 초기화 시켰다. (인덱스를 탐색하기 때문에 0번째 인덱스와 마지막 인덱스가 저장되는 경우 개수를 잘못 세는 경우가 존재하기 때문에)

전체 배열의 크기 => size

left에 충족되지 못하는 최대 크기의 인덱스 번호 => less

right에 충족되지 못하는 최소 크기의 인덱스 번호 => over

 

size - (size-over) - (less+1) 이라는 식이 나오게 된다.

 

문제에서 주어진 예시를 보면 이해하기가 수월할 것이다.

1 3 10 20 30 점 배열과, 주어진 범위가 2, 15인 경우를 살펴보면,

2보다 작은 수 중에 가장 큰 수 = 1    => 0번째 인덱스 ~> less = 0

15보다 큰 수 중에 가장 작은 수 = 20 => 3번째 인덱스 ~> over =3

 

size - (size-over) - (less+1)    =   5 - (5 - 3) - (0 +1)   ~> 총 5개 - right를 넘어가는 개수(2개) - left에 못미치는 개수(1개) = 2 가 나온다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long[] pointArr = new long[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)  pointArr[i] = Long.parseLong(st.nextToken());
        Arrays.sort(pointArr);

        StringBuffer sb = new StringBuffer();
        final String NEWLINE = "\n";
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            long left = Long.parseLong(st.nextToken());
            long right = Long.parseLong(st.nextToken());
            sb.append(getPoints(left,right,pointArr)).append(NEWLINE);
        }
        br.close();
        System.out.println(sb.toString());
    }

    private static int getPoints(long left, long right, long[] pointArr) {
        int size = pointArr.length;
        int leftIdx =0, rightIdx = size-1, less=-1, over=size;

        while(leftIdx <= rightIdx) {
            int midIdx = (leftIdx+rightIdx)/2;
            if(pointArr[midIdx] >= left) rightIdx = midIdx-1;	// 조건 충족 경우
            else {
                less = midIdx;
                leftIdx = midIdx+1;
            }
        }
        
        leftIdx =0;
        rightIdx=size-1;
        
        while(leftIdx <= rightIdx) {
            int midIdx = (leftIdx+rightIdx)/2;
            if(pointArr[midIdx] <= right) leftIdx = midIdx+1;	// 조건 충족 경우
            else {
                over = midIdx;
                rightIdx = midIdx-1;
            }
        }
        return size-(size-over)-(less+1);
    }
}