[백준] 26258번. 다중 일차 함수(JAVA)

문제

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

---

풀이(12분)

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

public class Main {

    static List<Point> points;

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

        int N = Integer.parseInt(br.readLine());
        points = new ArrayList<>();
        for(int i = 0; i  < N; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points.add(new Point(x, y));
        }
        Collections.sort(points);

        int Q = Integer.parseInt(br.readLine());
        for(int i = 0; i < Q; i++){
            double k = Double.parseDouble(br.readLine());
            int idx = binarySearch(k);
            int firstY = points.get(idx).y;
            int secondY = points.get(idx-1).y;
            if(firstY - secondY > 0){
                System.out.println(1);
            } else if (firstY - secondY < 0) {
                System.out.println(-1);
            }else{
                System.out.println(0);
            }
        }
    }

    static int binarySearch(double target){
        int start = 0;
        int end = points.size() - 1;
        int mid = (start + end) / 2;
        while(start <= end){
            mid = (start + end) / 2;
            if(points.get(mid).x < target){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        return start;
    }

    static class Point implements Comparable<Point>{
        int x, y;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }


        @Override
        public int compareTo(Point o) {
            return this.x  - o.x;
        }
    }

}

---

문제 풀이 전략

 

문제의 조건을 정확히 읽으면 이분탐색이라는 걸 잡아내기 어렵지는 않았다.

 

문제의 좌표평면을 보면 xi,yi가 실수로 주어질 수도 있겠다 싶겠지만 자세히 보면 격자가 2칸으로 되어있고, 문제 조건 내에서도 정수로만 입력이 주어진다고 되어있다.

또한 k 역시 정수 포인트 위에 위치하지않고, 소수로만 존재한다.

 

즉, 점들을 x값을 기준으로 정렬한 뒤 어퍼바운드 이분탐색을 진행한다.

이분탐색이 된 결과의 로우바운드, 어퍼바운드의 y값을 비교하여 증감을 구분하면 된다.