코딩테스트 준비 F - 선분 위의 점

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 11663.선분 위의 점
사용언어 : C#
난이도 : Middle
풀이시간 : 1h 28m ++
유형 : 이분 탐색

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

문제 풀이 접근

이 문제의 초기 아이디어는 주어지는 점에 대해서 영역을 구해서, 인덱스를 연산하여 사이에 있는 갯수를 구하는 방식이다.

문제를 풀면서 순서는 아래와 같이 생각했다.
1. 초기 영역이 주어지는 선분이 점들의 집합에서 벗어나는 경우, left는 arr[0] 인덱스로 맞춰주고,
right는 arr[arr.Length-1]로 맞춰서 벗어나는 선분을 점의 집합 안에 들어올 수 있도록 조정한다.
2. 이후 선분을 점들의 포지션으로 서서히 당기면서 선분을 포함하는 점의 시작과 점의 끝의 값과 같다면
인덱스를 연산해서 포함되는 점의 집합수를 넘긴다.

초기 아이디어의 문제점은 정확하게 영역을 구해내기가 어려웠다.
문제에서 주어지는 TC의 영역을 정확히 구해내는 것이 쉽지 않아서 푼 사람들의 코드를 참고해보니, while을 두 번 사용하여 왼쪽, 오른쪽을 구별해 연산하는 방식이 일반적이었다.

작성 코드 (C#) - 실패

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

/*
 * Difficulty : 
 * URL : https://www.acmicpc.net/problem/11663
 * Time : 1h 28m ++
 */

public struct Point
{
    public int a;
    public int b;

    public Point(int a, int b)
    {
        this.a = a;
        this.b = b;
    }
}

//10 5
//1 3 7 10 15 16 20 28 39 40
//1 2
//1 4
//1 10
//10 11
//15 20



namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public int _n;
        public int _m;

        public int[] _dot;
        public Point[] _point;

        public StringBuilder _sb;

        public void solve(){
            _sb = new StringBuilder();
            string[] _input = Console.ReadLine().Split(' ');
            _n = int.Parse(_input[0]);
            _m = int.Parse(_input[1]);

            _dot = new int[_n];
            Array.Sort(_dot);

            _input = Console.ReadLine().Split(' ');
            for(int i = 0; i < _n; ++i)
                _dot[i] = int.Parse(_input[i]);

            _point = new Point[_m];

            for(int i = 0; i < _m; ++i)
            {
                _input = Console.ReadLine().Split(' ');
                _point[i].a = int.Parse(_input[0]);
                _point[i].b = int.Parse(_input[1]);
            }

            for(int i = 0; i < _point.Length; ++i)
            {
                int _ret = 0;
                int _maxDot = _dot.Length - 1;
                if (_point[i].a > _dot[_maxDot] || _point[i].b < _dot[0])
                {

                }
                else
                {
                    _ret = BinarySearch(_dot, _point[i]);
                }
                _sb.Append(_ret.ToString());
                _sb.Append('\n');
            }
 
            Console.WriteLine(_sb.ToString());
        }

        public int BinarySearch(int[] _arr, Point _pt)
        {
            int left = 0;
            int right = _arr.Length - 1;

            int _leftIdx = 0;
            int _rightIdx = 0;

            while (left <= right)
            {
                int mid = (left + right) / 2;

                if (_arr[mid] < _pt.a)
                {
                    left = mid + 1;
                }
                else
                {
                    _leftIdx = mid;
                    right = mid - 1;
                }
            }

            left = 0;
            right = _arr.Length - 1;

            while (left <= right)
            {
                int mid = (left + right) / 2;

                if (_arr[mid] > _pt.b)
                {
                    right = mid -1;
                }
                else
                {
                    _rightIdx = mid;
                    left = mid + 1;
                }
            }

            return _rightIdx - _leftIdx +1;
        }
    }
}

코드 결과

** 정확히 풀었다고 생각했는데, 다시 풀어야할 듯하다.