boj 11663: 선분 위의 점

일단 아이디어 자체는 왼쪽에서 포함되는 점의 위치 leftIndex와 오른쪽에서 포함되는 점의 위치 rightIndex를 각각 구한 뒤,

rightIndex - leftIndex + 1 을 하여 구해 보자는 생각이었다.

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

public class Main {

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

		int points = Integer.parseInt(st.nextToken());
		int lines = Integer.parseInt(st.nextToken());

		int point[] = new int[points];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < points; i++) {
			point[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(point);

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < lines; i++) {
			st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());

			int rightIndex = getRightIndex(right, points - 1, point);
			int leftIndex = getLeftIndex(left, points - 1, point);
			// System.out.println(leftIndex + " " + rightIndex);
			int sum = rightIndex - leftIndex + 1;
			sum = Math.max(0, sum);
			bw.write(sum + "\n");
		}
		bw.flush();
		br.close();
	}

	private static int getLeftIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = end;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (target < point[mid]) {
				answer = Math.min(answer, mid);
				end = mid - 1;
			} else if (target == point[mid]) {
				return mid;
			} else {
				start = mid + 1;
			}
		}
		return answer;
	}

	private static int getRightIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = 0;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (point[mid] < target) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else if (point[mid] == target) {
				return mid;
			} else {
				end = mid - 1;
			}
		}
		return answer;
	}
}

 

하지만, 0이나 40과 같이 범위를 벗어나는 선분인 경우 따로 처리가 필요했다.

(예를 들어 선분 40 40 의 경우 기존 코드에서는 범위에 벗어난 선분이지만 점 1개를 리턴하고 있었다.)

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

public class Main {

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

		int points = Integer.parseInt(st.nextToken());
		int lines = Integer.parseInt(st.nextToken());

		int point[] = new int[points];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < points; i++) {
			point[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(point);

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < lines; i++) {
			st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());

			int rightIndex = getRightIndex(right, points - 1, point);
			int leftIndex = getLeftIndex(left, points - 1, point);
			// System.out.println(leftIndex + " " + rightIndex);
			int sum = calcPoints(leftIndex, rightIndex, points);
			bw.write(sum + "\n");
		}
		bw.flush();
		br.close();
	}

	private static int calcPoints(int leftIndex, int rightIndex, int length) {
		if (rightIndex < 0 && leftIndex < 0) {
			return 0;
		}

		if (rightIndex >= length && leftIndex >= length) {
			return 0;
		}

		if (leftIndex < 0 && rightIndex >= length) {
			return length;
		}

		if (leftIndex < 0) {
			return rightIndex + 1;
		}

		if (rightIndex >= length) {
			return length - leftIndex;
		}

		return rightIndex - leftIndex + 1;
	}

	private static int getLeftIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = end;

		if (target < point[0]) {
			return -1;
		}
		if (point[end] < target) {
			return end + 1;
		}

		while (start <= end) {
			int mid = (start + end) / 2;

			if (target < point[mid]) {
				answer = Math.min(answer, mid);
				end = mid - 1;
			} else if (target == point[mid]) {
				return mid;
			} else {
				start = mid + 1;
			}
		}
		return answer;
	}

	private static int getRightIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = 0;

		if (target < point[0]) {
			return -1;
		}
		if (point[end] < target) {
			return end + 1;
		}

		while (start <= end) {
			int mid = (start + end) / 2;

			if (point[mid] < target) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else if (point[mid] == target) {
				return mid;
			} else {
				end = mid - 1;
			}
		}

		return answer;
	}
}

이렇게 귀찮아질 바에는 반대로 생각하면 조금 더 쉬워진다. 지금은 포함되는 점의 시작점, 끝점을 구했지만

포함되지 않는 부분의 점들을 구하게 된다면 풀이는 조금 더 간단해 질 수 있음..