가장 가까운 두 점
-
[백준 - 2261번] 가장 가까운 두 점 - Java //Wello Horld//Algorithm/BOJ(Baekjoon Online Judge) 2019. 7. 25. 23:39
이번에는 BOJ의 2261번 문제 "가장 가까운 두 점" 문제를 풀어보도록 하자 문제는 간단한데, 풀이가 까다로운 문제이다. 먼저, 입력으로 점의 개수 n이 주어지고, 그다음 줄부터 n줄 만큼 각 점의 x, y 의 좌표가 공백을 사이에 두고 주어진다. 그리고 가장 가까운 두 점의 거리의 제곱값을 출력하면 되는 문제이다. 이 문제를 풀 때, 아래와 같이 하나하나씩 비교해주게 되면, 점이 최대로 많을 때, 100,000(개)가 존재하고, 시간 복잡도가 O(N^2)가 되기 때문에 거의 10,000,000,000(백억)번 정도 루프를 돌려주게되어서, 시간초과가 떠버린다. import java.io.*; import java.util.*; public class Main { public static void ma..