정렬 알고리즘 예제(2). 백준 [11651] 좌표 정렬하기 2

백준[11651] - 좌표 정렬하기 2

우선적으로 y를 기준으로 정렬하고 같다면 x를 기준으로 정렬하는 문제이다. 

좌표를 저장할 때, 이차원 배열에 저장할까, x배열, y배열을 이용하여 index로 관리할까 고민해 봤지만, Pair라는 class를 정의해 문제를 풀면 간단할 거라고 생각이 들었다.

Pair라는 클래스를 정의하는데 Comparable interface를 구현하게 만들어 우선순위 큐를 이용하여 출력한다면, 한번에 문제를 풀 수 있다.

다음은 Java로 작성한 코드이다.

import java.util.PriorityQueue;
import java.util.Scanner;

public class Coordinate {

	public static void main(String[] args) {
		
		//Pair class 정의
		class Pair implements Comparable<Pair>{
			public Pair(int a,int b) {
				x = a;
				y = b;
			}
			int x,y;
			@Override
			public int compareTo(Pair o) {
				if(this.y == o.y) {
					return x - o.x;
				}
				return y - o.y;
			}
			
			public String toString() {
				return (x + " " + y);
			}
		}
		

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		
		//우선 순위 큐 정의 
		PriorityQueue<Pair> q = new PriorityQueue<Pair>();
		int x,y;
		
		//n만큼 좌표를 입력 받기
		for (int i = 0; i < n; i++) {
			x = scan.nextInt();
			y = scan.nextInt();
			q.add(new Pair(x,y));
		}
		
		//출력
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}

}

Comparable interface를 구현하는 Pair클래스를 만들었다. 
우선순위 큐에 의해 Pair클래스는 정렬이 되는데 정렬되는 기준을 사용자가 임의로 설정할 수 있다.
문제에서와 같이 y가 같지 않다면 y를 기준으로, 같다면 x를 기준으로 정렬이 되게 하였고, toString 함수를 구현하여 출력도 문제 양식에 맞추어 출력이 되게 만들었다.