백준 11650번 좌표 정렬하기 :: 마이구미

이번 글은 백준 11650번 좌표 정렬하기 문제를 다룰 것이다.

문제는 간단하다.

백준 11650번 좌표 정렬하기

https://www.acmicpc.net/problem/11650

백준 11650번 좌표 정렬하기 2

https://www.acmicpc.net/problem/11651 

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

문제에 보다시피 정렬하는 문제이다.

1차원적인 문제라면 정렬 문제는 정말 쉽다.

본인의 경우는 큰 어려움이 없는 한 Arrays.sort()를 통해 처리한다.

하지만 이렇게 2개 이상의 기준을 가진다면 조금 까다롭게 느껴진다.

이전 글에서도 정렬 문제를 다룬 적이 2번 있다.

2번 모두 compare 메소드를 오버라이딩하는 방식으로 이용하였다.

http://mygumi.tistory.com/44

http://mygumi.tistory.com/48

이 문제 또한 같은 방식을 이용할 것이다.

위의 링크의 문제들도 풀어본다면 많은 도움이 되니 풀어보길.....

일단 문제를 어떻게 접근할 것인지 보자.

x좌표와 y좌표를 비교해야하니 당연히 1차원 배열은 안된다.

그렇다면 hashmap을 생각할 수도 있다.

x좌표를 key로 두고, y좌표를 value로 두면 된다.

하지만 key가 중복될 수도 있으니 힘들다.

편하게 class 하나 만들어 사용하자.

class Point {
	int x;
	int y;

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

그리고 제일 중요한 compare 메소드를 오버라이딩 해보자.

주어진 정렬 기준은 간단하다.

x좌표를 기준으로 정렬, 같다면 y좌표를 기준으로 정렬.

class ComparatorAscending implements Comparator<Point> {
	@Override
	public int compare(Point p1, Point p2) {
		// TODO Auto-generated method stub
		if (p1.y < p2.y) {
			return -1;
		} else if (p1.y == p2.y) {
			if (p1.x < p2.x) {
				return -1;
			} else {
				return 1;
			}
		} else {
			return 1;
		}
	}
}

자세한 것들은 생략하겠다. (위 이전에 작성된 두개의 링크 참조)

간단하게 오버라이딩을 만들어보았다.

이러한 방식으로 많은 정렬문제를 해결할 수 있다.

그러니 이 문제를 포함하고도 이전의 작성된 2개의 문제가 있다.

꼭 풀어보고 습득하길 바란다.

Github - https://github.com/hotehrud/acmicpc

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Main {
    static PriorityQueue<Point> q = new PriorityQueue<Point>(new ComparatorAscending());
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int t = Integer.parseInt(br.readLine().trim());
        Point point;
 
        String s[] = new String[2];
        for (int i = 0; i < t; i++) {
            s = br.readLine().split(" ");
 
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
 
            point = new Point(x, y);
 
            q.add(point);
        }
 
        for (int i = 0; i < t; i++) {
            Point pp = q.poll();
            sb.append(pp.x + " " + pp.y + "\n");
        }
        System.out.println(sb.toString());
    }
}
 
class ComparatorAscending implements Comparator<Point> {
    @Override
    public int compare(Point p1, Point p2) {
        // TODO Auto-generated method stub
        if (p1.y < p2.y) {
            return -1;
        } else if (p1.y == p2.y) {
            if (p1.x < p2.x) {
                return -1;
            } else {
                return 1;
            }
        } else {
            return 1;
        }
    }
}
 
class Point {
    int x;
    int y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}