자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 좌표 정렬

 

https://hyejin.tistory.com/1245

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 장난 꾸

-> 이전 문제 풀이 

 

 

7. 좌표 정렬 

설명

N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.

정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.

 

입력

첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.

두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.

 

출력

N개의 좌표를 정렬하여 출력하세요.

 

예시 입력 1 

5
2 7
1 3
1 2
2 5
3 6

 

예시 출력 1

1 2
1 3
2 5
2 7
3 6

 

 

문제 풀이 1

public class CoordinateAlignment
{
   public static void main(String[] args)
   {
      CoordinateAlignment coordinateAlignment = new CoordinateAlignment();
      Scanner scanner = new Scanner(System.in);
      
      int n = scanner.nextInt();
      ArrayList<Point> points = new ArrayList<>();
      for (int i = 0; i < n; i++)
      {
         points.add(new Point(scanner.nextInt(), scanner.nextInt()));
      }
      
      ArrayList<Point> result = coordinateAlignment.solution(n, points);
      for (Point point : result)
      {
         System.out.println(point.x + " " + point.y);
      }
      
   }
   
   public ArrayList<Point> solution(int n, ArrayList<Point> points)
   {
      Collections.sort(points, (o1, o2) -> {
         if (o1.x == o2.x) {
            return o1.y - o2.y;
         }else {
            return o1.x - o2.x;
         }
      });
      return points;
   }
   
}

class Point
{
   int x;
   int y;
   
   public Point(int x, int y)
   {
      this.x = x;
      this.y = y;
   }
   
   @Override
   public String toString()
   {
      return "Point{" +
            "x=" + x +
            ", y=" + y +
            '}';
   }
   
}

 

👩🏻‍💻 : 나는 우선 좌표 정렬이라고 해서 Point라는 클래스를 만들고 이 클래스를 가지고 정렬해야 겠다고 생각했다.

그래서 먼저 Point 라는 클래스를 만들고, Scanner 를 통해 좌표를 입력 받으면 Point 객체를 하나씩 생성해서 Arraylist에 담아줬다. 

 

그 다음 Collection.sort메서드를 이용해서 points 리스트를 오름차순으로 정렬해줄 것인데 이때 람다식으로 o1, o2  Point 객체가 주어질 때, 만약 o1.x와 o2.x 가 같으면 o1.y - o2.y 로 뺀 값을 리턴해줬다. 

그리고 o1.x와 o2.x가 다르면 o1.x - o2.x 값을 리턴해주면 

우선 x 값에 의해 오름차순 정렬을 하고, x의 값이 같으면 y 값을 기준으로 오름차순 정렬을 한다. 

 

 

 

문제 풀이 2

public class PointAlignment {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Point2> point2s = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            point2s.add(new Point2(scanner.nextInt(), scanner.nextInt()));
        }

        Collections.sort(point2s);

        System.out.println("point2s = " + point2s);
    }
}

class Point2 implements Comparable<Point2> {
    int x, y;

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

    @Override
    public int compareTo(Point2 o) {
        if (this.x == o.x) {
            return this.y - o.y; // 오름차순은 음수 값이 나와야함
        } else {
            return this.x - o.x;
        }
    }

    @Override
    public String toString() {
        return "Point2{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

👾 : 강사님도 나와 비슷하게 Point 클래스를 생성하였는데 Point 클래스에서 Comparable 인터페이스를 상속받고, compareTo메서드를 구현했다. Point2의 o 객체가 매개변수로 주어지는데, 오름차순 정렬을 하기 위해서는 this.x와 o.x 가 같을 경우에는 this.y - o.y 를 해주고, this.x와 o.x의 값이 다를 경우에는 return this.x- o.x의 값을 리턴해주면 된다. 

 

강사님은 따로 solution 메서드를 만들지 않고, for문을 통해서 Arraylist<Point2> 리스트를 만들고, 그 리스트를 Collection.sort 메서드에 넣어줘서 오름차순 정렬을 만들고 출력해줬다. 

 

만약 내림차순 정렬을 해주고 싶다하면 반대로 o.x - this.x 를 해줘야 한다. 

 

 

 

💭 좌표 관련 문제는 이렇게 Point 클래스를 하나 만들고 그 클래스를 통해 문제를 해결해야 한다 !!