[코드트리 조별과제] Grid Compression

좌표 정보를 문제를 풀기위해 재정렬 하는 과정이라고 생각하면 편하다.

 

보통 일정 범위내의 수직선에서, 특정 구간내 점의 개수를 구하는 문제를 볼 수 있다.

 

이럴 때, 모든 점을 해당 수 범위내에 표기하기 위해서 점이 있다 없다를 기준으로 boolean 배열을 사용하곤 한다.

 

그렇지만 이는 index == 점위치 가 되기 때문에 점의 값이 사실상 억을 넘어서면 "메모리 초과" 를 당하거나 안당하더라도 순회하면서 점을 전처리하는데 시간 복잡도를 초과할 가능성이 크다.

 

여기서 볼 수 있는 관찰은, 전처리를 해야함을 인지하였으나 주어진 점들을 표기하는 방법에 있어서 문제가 있다.

 

일반적으로 숫자가 매우 큰 상황에서 해당 숫자를 인덱스로 사용해야 한다면 배열이 아닌 HashMap을 사용하면 좋다.

 

왜냐하면 HashMap의 경우 점이 중복되더라도 카운팅 할 수 있기 때문이다.

 

그리고 수직선내의 구간 점개수는 중요한 힌트로서 숫자가 커질수록 포함되는 점의 개수가 커진다는 것

 

이말을 다시 해석하자면, 수직선상의 점 N개가 주어졌을 때,  어떤수 x까지의 점의 개수는 정렬 후의 x의 순서와 동일하다.

 

아래의 코드는 점의 범위이자 즉 수직선의 범위가 -10억에서 +10억이고 10만개의 선분이 주어질때, 각 선분내에 몇개의 점이 포함되는지 쿼리를 처리하는 문제이다.

 

이문제는 그래도 친절하게 "주어진 구간에 해당하는 양끝점이 무조건 이전에 주어진 점들 중 하나라는 점"이다.

 

그렇다는것은 HashMap을 통해 해당 점 까지의 총 점의 개수를 구하면 된다.

 

여기서 하나의 skill이라고 하면 주어진 점들을 다 받아서 정렬해도 되지만, TreeSet을 쓴다면 좀 더 간단하다.

 

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

public class Main {
    static StringTokenizer stk;
    static int n, q;
    static int[] points;
    static int[][] lines;
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(stk.nextToken());
        q = Integer.parseInt(stk.nextToken());
        
        points = new int[n];

        stk = new StringTokenizer(bf.readLine());
        TreeSet<Integer> pointCnt = new TreeSet<>();
        for(int i= 0;i<n;i++){
            points[i] = Integer.parseInt(stk.nextToken());
            pointCnt.add(points[i]);
        }

        // -3까지 1, 5까지 2, 9까지 3

        int cnt = 1;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for(int point: points){
            hashMap.put(pointCnt.pollFirst(), cnt++);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<q;i++){
            stk = new StringTokenizer(bf.readLine());
            int s = Integer.parseInt(stk.nextToken());
            int e = Integer.parseInt(stk.nextToken());
            sb.append(hashMap.get(e) - hashMap.get(s) + 1).append("\n");
        }
        System.out.print(sb);
    }
}

 

물론 주어진 문제는 이렇게 푸는것이 가장 빠른 방법이겠지만

 

만약 주어진 선분의 양끝점이 이전에 주어진 점들에 포함되지 않을수 있다라는 조건이 추가된다면

 

주어진 점들의 양끝점에 해당하는 상한경계와 하한경계를 구하는것이 정답이 된다.

 

필자는 위의 중요한조건을 보지못하여 초안에 아래와 같은 코드를 만들었다.

 

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

public class Main {
    static StringTokenizer stk;
    static int n, q;
    static int[] points;
    static int[][] lines;
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(stk.nextToken());
        q = Integer.parseInt(stk.nextToken());
        
        points = new int[n];
        lines = new int[q][2];
        stk = new StringTokenizer(bf.readLine());
        
        for(int i= 0;i<n;i++){
            points[i] = Integer.parseInt(stk.nextToken());
        }

        // -3까지 1, 5까지 2, 9까지 3
        Arrays.sort(points);
        
        TreeMap<Integer, Integer> pointCnt = new TreeMap<>();

        int cnt = 1;

        for(int point: points){
            pointCnt.put(point, cnt++);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<q;i++){
            stk = new StringTokenizer(bf.readLine());
            int s = Integer.parseInt(stk.nextToken());
            int e = Integer.parseInt(stk.nextToken());

            int under = pointCnt.get(pointCnt.floorKey(s));
            int upper = pointCnt.get(pointCnt.ceilingKey(e));
            sb.append(upper - under + 1).append("\n");
        }
        System.out.print(sb);
    }
}

 

아래의 코드가 더 느리다. 왜냐하면 floorKey와 ceilingKey를 하면서 log연산이 q만큼 돌아가기 때문이다.