[자바] 백준 11663 - 선분 위의 점 (java)

 문제 : boj11663

---

 

필요 알고리즘 개념

• 정렬, 해시, 이분 탐색, 누적합
  
  • 이분 탐색을 활용하는 문제이다. 내 경우엔 prefix sum 개념도 좀 들어갔다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  [a, b] 이내에 포함된 점을 알려면 '[0, b]에 포함된 점의 개수 - [0, a-1]에 포함된 점의 개수' 를 구하면 될 것이다. (누적합 알고리즘 개념)

 

  그럼 임의의 x에 대해 [0, x]에 포함된 점의 개수를 어떻게 구할 수 있을까? N개의 입력값을 정렬한 후, 작은 값부터 1개씩 더해진다고 생각하면 된다. 즉 예제 입력 1의 경우 아래와 같다. 이하의 값에 대해 x를 key로, [0,x]내의 점의 수를 value로 하는 HashMap으로 기록해두면 x만 구하면 O(1)로 범위 내의 점의 수를 알 수 있다.

 

  그럼 이제 입력으로 a와 b가 주어졌을 때, [0,b]의 점의 수와 [0,a-1]의 점의 수만 구하면 된다. 그럴려면 a보다 작은 것 중 가장 큰 x의 값과, b보다 작거나 같은 것 중 가장 큰 x값을 찾을 수 있으면 된다. 이걸 이분 탐색으로 찾으면 될 것이다. 자바의 경우 TreeSet을 사용하면 이분 탐색을 쉽게 구현할 수 있다. 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<13);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        TreeSet<Integer> ts = new TreeSet<>();
        HashMap<Integer, Integer> hs = new HashMap<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            hs.put(arr[i], ++cnt);
            ts.add(arr[i]);
        }

        StringBuilder sb = new StringBuilder();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            Integer a = Integer.parseInt(st.nextToken());
            Integer b = Integer.parseInt(st.nextToken());
            a = ts.lower(a);
            b = ts.floor(b);
            a = a==null? 0 : hs.get(a);
            b = b==null? 0 : hs.get(b);
            sb.append(b-a).append('\n');
        }
        System.out.print(sb);
    }
}