2회차 - 알고리즘 기록

📌문제2F-데스티니

감수성이 풍부한 명은이는 매일 밤 하늘을 바라 본다.

어느 날 명은이는 태양을 중심으로 공전하는 지구와 또 그 지구를 중심으로 공전하는 달의 관계를 보며 깊은 고뇌에 빠졌다.

그 천체들은 계속 주위를 멤돌면서도 결국 일정거리 이상으로 가까워 질 수 없는 운명이기 때문이다.

명은이는 다음과 같은 생각을 하게 되었다.

 

"지금 하늘에 떠 있는 천체들 중 서로 가장 가까이 있는 쌍은 무엇일까?"

 

 감수성이라곤 찾아볼 수 없는, 뼛속까지 이과인 당신은 실제로 천체들간의 거리를 측정하여 가장 가까이 있는 두 천체를 명은이에게 알려주려고 한다. 가장 가까이 위치한 두 천체를 찾아보자.

 

입력 형식

 첫 줄에는 하늘에 떠 있는 천체의 수 N이 주어진다. N은 2이상 1,000이하의 자연수이다.

그 후 총 N줄에 걸쳐서 각 줄에는 한 천체의 위치를 좌표로 나타내는 두 정수가 주어진다.

천체의 정보를 포함하는 N개의 각 줄에는 천체의 x좌표와 y좌표를 나타내는 두 정수가 공백으로 구분되어 주어진다.

모든 좌표는 절대값이 1만 이하인 정수이다.

모든 천체의 좌표는 서로 다르다.

 

출력 형식

 첫 줄에는 가장 가까운 두 천체의 거리를 소수점 두 번째 자리에서 반올림하여 첫 번째 자리까지 출력한다.

두 번째 줄에는 그 거리만큼 떨어진 천체 쌍의 수를 출력한다.

 

예시

- 입력

 

5
10000 9999
-10000 -9999
10000 -9999
-10000 9999
0 0

 

- 출력

1.4

1

 

생각 풀이

아니 이게 뭐람 ? 내가 이걸 어떻게 암 ?

이 문제는 내 머릿속에서 접근불가이다.

강의 찬스를 써야겠다 : )

이해도가 낮다. 아니 없다.

이거는 시간날 때 하나하나 짚어봐야겠다 : (

 

코드 풀이

 

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


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	public static void main(String[] args)
	{
		int n = scanner.nextInt();
		Point2D[] points = new Point2D[n];

		for(int i = 0 ; i < n ; i++)
		{
			int x=  scanner.nextInt();
			int y=  scanner.nextInt();
			points[i] = new Point2D(x, y);
		}
		
		// points => n 개의 점의 배열
		int minDist = Integer.MAX_VALUE;
		int minCount = 0;
		
		for( int i = 0; i < n; i ++ ){
			for( int j = 0; j < i; j ++ ){
				int sqd = points[i].getSquaredDistanceTo(points[j]);
				if(sqd < minDist){
					minDist = sqd;
					minCount = 1;
					
					// 갱신은 안일어났지만 최소거리 가진 쌍 발견
				}else if(sqd == minDist){
					minCount++;
				}
			}
		}
		System.out.printf("%.1f\n", Math.sqrt(minDist));
		System.out.printf("%d", minCount);
	}
}

class Point2D{
	int x;
	int y;
	public Point2D(int x, int y){
		this.x = x;
		this.y = y;
	}

	/**
	 * 2차원 평면 상에서 점 this부터 점 target까지 거리의 제곱을 계산하는 함수
	 * @param target
	 * @return
	 */
	public int getSquaredDistanceTo(Point2D target){
		int deltaX = this.x - target.x;
		int deltaY = this.y - target.y;
		return (deltaX * deltaX) + (deltaY * deltaY);
	}

	public double getDistanceTo(Point2D target){
		return Math.sqrt(this.getDistanceTo(target));
	}
}

---

minDist 에는 int  최대값을 할당해준다.

 

입력 받은 값을 Point2D 의 객체에 넣고 points[] 의 배열에 차곡차곡 담는다.

 

그리고 아래와 같이 모든 배열을 순회를 한다.

 

points[0] 번 부터 points[0],points[1],points[2], points[3], points[4]

points[1] 번 부터 points[0],points[1],points[2], points[3], points[4]

points[2] 번 부터 points[0],points[1],points[2], points[3], points[4]

points[3] 번 부터 points[0],points[1],points[2], points[3], points[4]

points[4] 번 부터 points[0],points[1],points[2], points[3], points[4]

 

getSquaredDistanceTo 메소드는 현재 자신의 x, y 와 비교해야 하는 target 의 x, y 의 차이를 x, y 를 거듭제곱한 후에 더한 값을 반환한다.

이때 반환되는 값이 this 와 target 의 차이다.

 

minDist 에서 가장 작은 거리를 가지고 있고, minCount 는 가장 작은 거리의 수를 가지고 있다.

minDist 의 값이 getSquaredDistanceTo 에서 반환된 값과 차이가 적다면 minDist 값에 반환 값을 대입한다.

 

그렇게 모든 값을 돌다가 minDist 값과 같다면 minCount 값을 올려준다.

새로운 minDist 값이 나온다면 minCount 값도 새로 세팅해준다. !

---

솔직히 연산을 하나하나 이해하니 이해는 가지만 문제를 보고 혼자 해결해나갈 자신은 없다.

아직 많이 부족하다. 

---