[백준] 2171번: 직사각형의 개수

문제

백준 - 2171번: 직사각형의 개수

분석

N개의 점의 정보가 주어졌을 때, 4개의 점이 이루는 사각형이 x축과 y축에 평행한 사각형들의 개수를 세는 문제이다.

두 x좌표 (x1, x2)가 같지 않아야 하고,
해당하는 x좌표에서 같은 y좌표 두 개 (y1, y2)가 있어야 한다.
→ 즉, (x1, y1), (x1, y2), (x2, y1), (x2, y2)가 있어야 직사각형이 만들어짐

Map<Integer, List> 형태로, 각 x좌표마다 존재하는 y좌표들을 저장한다.
x1과 x2를 각각 선택했을 때 매핑된 y의 개수가 2보다 작으면 넘어간다.
x1에 존재하는 y1과 y2를 선택했을 때 그 값이 x2에도 존재하면 조건을 만족하는 사각형이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int N;
	static int[][] points;
	static Map<Integer, List<Integer>> point_lst;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		points = new int[N][2];
		point_lst = new HashMap<>();

		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[i][0] = x;
			points[i][1] = y;
			if (!point_lst.containsKey(x))
				point_lst.put(x, new ArrayList<>());
			point_lst.get(x).add(y);
		}

		List<Integer> xList = new ArrayList<>(point_lst.keySet());

		int res = 0;

		for (int i = 0; i < xList.size(); i++) {
			int x1 = xList.get(i);
			List<Integer> yList1 = point_lst.get(x1);
			if (yList1.size() < 2)
				continue;

			for (int j = i + 1; j < xList.size(); j++) {
				int x2 = xList.get(j);
				List<Integer> yList2 = point_lst.get(x2);
				if (yList2.size() < 2)
					continue;

				for (int k = 0; k < yList1.size(); k++) {
					int y1 = yList1.get(k);
					for (int l = k + 1; l < yList1.size(); l++) {
						int y2 = yList1.get(l);
						if (yList2.contains(y1) && yList2.contains(y2)) {
							res++;
						}
					}
				}
			}
		}

		System.out.println(res);
		br.close();
	}
}

Map<Integer, Set> 형태로 자료구조를 사용하면 더 빠르게 실행된다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int N;
	static Map<Integer, Set<Integer>> point_lst;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		point_lst = new HashMap<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			if (!point_lst.containsKey(x))
				point_lst.put(x, new HashSet<>());
			point_lst.get(x).add(y);
		}

		List<Integer> xList = new ArrayList<>(point_lst.keySet());

		int res = 0;

		for (int i = 0; i < xList.size(); i++) {
		    int x1 = xList.get(i);
		    Set<Integer> ySet1 = point_lst.get(x1);
		    if (ySet1.size() < 2)
		        continue;

		    for (int j = i + 1; j < xList.size(); j++) {
		        int x2 = xList.get(j);
		        Set<Integer> ySet2 = point_lst.get(x2);
		        if (ySet2.size() < 2)
		            continue;

		        for (Integer y1 : ySet1) {
		            for (Integer y2 : ySet1) {
		                if (y1 >= y2) continue; 
		                if (ySet2.contains(y1) && ySet2.contains(y2)) {
		                    res++;
		                }
		            }
		        }
		    }
		}


		System.out.println(res);
		br.close();
	}
}