코드트리 [자바 java] 점 개수 세기 3

https://www.codetree.ai/missions/8/problems/count-number-of-points-3?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

점의 위치가 주어지고, 특정 범위가 주어지면 그 사이에 있는 점들의 갯수를 출력하는 문제이다.

범위만큼의 배열을 만들고, 브루트포스로 하나하나 탐색해가는 방법도 물론 존재하지만, 이렇게 하면 시간이 오래 걸린다. 그래서 이 문제에서 사용한 방법은 좌표압축이다.

 

Arrays.sort를 이용해서 입력받은 점들의 위치를 정렬했고, 이들의 수와 index값을 묶어서 HashMap에 저장했다. 

그 다음 범위가 하나씩 입력될 때마다 그 범위에 해당하는 index값을 받아 start값과 end값의 차이를 빼서 두 점 사이에 있는 점들의 갯수를 출력하도록 했다.

 

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


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 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());
        }

        HashMap<Integer,Integer> hash = new HashMap<>();

        //정렬

        Arrays.sort(arr);

        //점 위치별 번호 매기기


        for(int i = 0;i<n;i++){
            hash.put(arr[i],i);
        }

        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            //입력받은 점들의 사이에 있는 점 수 출력


            System.out.println(Math.abs(hash.get(s) - hash.get(e))+1);


        }

    }
}