[코드트리/NOVICE MID] 원점으로부터의 거리 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Point implements Comparable<Point> {
    int idx, x, y;
 
    public Point(int idx, int x, int y) {
        this.idx = idx;
        this.x = x;
        this.y = y;
    }
 
    @Override
    public int compareTo(Point p) {
        int d1 = Math.abs(this.x) + Math.abs(this.y);
        int d2 = Math.abs(p.x) + Math.abs(p.y);
 
        if(d1 != d2) {    // 원점에서 가까운 점부터 순서대로 출력
            return d1 - d2;
        }
        return this.idx - p.idx;    // 거리가 같은 점이 여러 개면, 번호가 작은 점부터
    }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        Point[] points = new Point[n];
        for(int i = 0 ; i < n ; i++) {
            String[] str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
 
            points[i] = new Point(i + 1, x, y);
        }
        
        Arrays.sort(points);
 
        for(Point p : points) {
            System.out.println(p.idx);
        }
    }
}

 

 

🧩  해결 아이디어

• 사용자 정의 정렬

점의 번호를 출력해야 하므로, Point 객체에 점 번호 값(idx)을 저장해 사용한다.

 

- 두 점의 거리가 다르다면, 원점에서 가까운 순서대로 출력한다.

- 두 점의 거리가 같다면 = 거리가 같은 점이 여러 개라면, 원점과 더 가까운 순(= 번호 오름차순)으로 출력한다. 

 

 

 

---

🔺 다른 풀이들

- N개의 점을 입력받을 때마다 리스트에 (각 점과 원점 사이의 거리, 인덱스)를 저장해 사용할 수도 있다.

 

---

💬 느낀 점

이거지  이거지....!!!

 

 

1회독	2회독	3회독	4회독	5회독
V