프로그래머스 / 예선캠핑

https://school.programmers.co.kr/learn/courses/30/lessons/1833

1. 누적합을 2차원으로 이용한다. (일종의 DP)
2. 좌표를 그대로 쓰면 불필요하게 넓은 공간을 사용해야 한다. 2^31-1 개의 공간에 5000개의 좌표. 

파이썬

from itertools import combinations


def solution(n, data):
    # x좌표 추출 -> 정렬 후 인덱스를 붙인 뒤 '값: 인덱스'로 딕셔너리에 저장,
    # 값으로 인덱스를 찾을 수 있도록 한다. y 좌표들도 마찬가지...
    x_dic = {x: i for i, x in enumerate(sorted({each[0] for each in data}))}
    y_dic = {y: i for i, y in enumerate(sorted({each[1] for each in data}))}

    # board를 만들기 위해 크기 확인
    x_size, y_size = len(x_dic), len(y_dic)

    # board 생성
    board = [[0 for _ in range(y_size)] for _ in range(x_size)]

    # 데이터 위치를 보드에 마킹. 위에서 만든 딕셔너리를 이용해서 좌표 변환.
    # 변환한 좌표를 data에 기록
    for i, (x, y) in enumerate(data):
        x, y = x_dic[x], y_dic[y]
        board[x][y] = 1
        data[i] = (x, y)

    # 데이터의 누적합을 구함. 2차원임에 유의하고, 겹치는 부분은 빼준다.
    for x in range(x_size):
        for y in range(y_size):
            board[x][y] += (board[x][y - 1] if y > 0 else 0) \
                           + (board[x - 1][y] if x > 0 else 0) \
                           - (board[x - 1][y - 1] if x > 0 and y > 0 else 0)

    answer = 0
    # 데이터에서 좌표를 2개 뽑아온다.
    # 겹치지 말아야하며, 순서가 없다. 조합이다.
    for d1, d2 in combinations(data, 2):

        # 쓰기 편하게 data를 언패킹 함.
        (x1, y1), (x2, y2) = d1, d2

        # 한 직선 위의 두 점이면 면적이 0
        if x1 == x2 or y1 == y2:
            continue

        # 최대 최소 정리.
        x_start, x_end = min(x1, x2), max(x1, x2)
        y_start, y_end = min(y1, y2), max(y1, y2)

        # 경계에는 쐐기가 있어도 텐트 설치에 지장이 없다.
        # 그러므로 경계에 있는 쐐기는 제외해야 한다.
        # 경계에 있는 쐐기를 제외하기 위해 end 좌표에서는 -1을 빼고
        # start 좌표에서는 start까지 제거.
        # 겹치는 부분 잘 처리한다.
        if board[x_end - 1][y_end - 1] \
                - board[x_end - 1][y_start] \
                - board[x_start][y_end - 1] \
                + board[x_start][y_start] == 0:
            answer += 1

    return answer


print(solution(4, [[0, 0], [1, 1], [0, 2], [200, 0]]))

자바

import java.util.*;

class Solution {
    int solution(int n, int[][] data) {
        var xList = new ArrayList<Integer>();
        var yList = new ArrayList<Integer>();

        for (var each : data) {
            xList.add(each[0]);
            yList.add(each[1]);
        }

        var uniqueXList = new ArrayList<>(new HashSet<>(xList));
        var uniqueYList = new ArrayList<>(new HashSet<>(yList));

        Collections.sort(uniqueXList);
        Collections.sort(uniqueYList);

        var xDic = new HashMap<Integer, Integer>();
        var yDic = new HashMap<Integer, Integer>();

        var index = 0;
        for (var x : uniqueXList)
            xDic.put(x, index++);

        index = 0;
        for (var y : uniqueYList)
            yDic.put(y, index++);

        var board = new int[xDic.size()][yDic.size()];
        for (var each : data)
            board[xDic.get(each[0])][yDic.get(each[1])] = 1;
        for (var x = 0; x < xDic.size(); x++)
            for (var y = 0; y < yDic.size(); y++)
                board[x][y] += (y > 0 ? board[x][y - 1] : 0)
                        + (x > 0 ? board[x - 1][y] : 0)
                        - (x > 0 && y > 0 ? board[x - 1][y - 1] : 0);

        var answer = 0;
        for (var i = 0; i < n; i++)
            for (var j = i + 1; j < n; j++) {
                var x1 = xDic.get(data[i][0]);
                var y1 = yDic.get(data[i][1]);
                var x2 = xDic.get(data[j][0]);
                var y2 = yDic.get(data[j][1]);

                if (Objects.equals(x1, x2) || Objects.equals(y1, y2))
                    continue;

                var xStart = Math.min(x1, x2);
                var xEnd = Math.max(x1, x2);
                var yStart = Math.min(y1, y2);
                var yEnd = Math.max(y1, y2);

                if (board[xEnd - 1][yEnd - 1]
                        - board[xEnd - 1][yStart]
                        - board[xStart][yEnd - 1]
                        + board[xStart][yStart] == 0)
                    answer++;
            }
        return answer;
    }
}