[백준 #11650] 좌표 정렬하기

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

 

문제

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

 

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 x_i와 y_i가 주어진다. (-100,000 ≤ x_,i y_i ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

 

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

 

예제 입력 1

5
3 4
1 1
1 -1
2 2
3 3

 

예제 출력 1

1 -1
1 1
2 2
3 3
3 4

 

해결 코드

import java.util.Scanner;
import java.util.List;
import java.util.Arrays;

public class Baekjoon11650 {
	
	public static class Coordinate {
		public int x;
		public int y;
		
		Coordinate(){}
		Coordinate(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int n;
	static Coordinate[] coordinateSet;
	
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		coordinateSet = new Coordinate[n];
		
		for(int i=0; i<n; i++) {
			int x = scanner.nextInt();
			int y = scanner.nextInt();
			coordinateSet[i] = new Coordinate(x, y);
		}
		
		Arrays.sort(coordinateSet, (a, b) -> {
			return Integer.compare(a.x, b.x);
		});;
		
		int start = 0;
		for(int i=0; i<n-1; i++) {
			if(coordinateSet[i].x != coordinateSet[i+1].x) {
				Arrays.sort(coordinateSet, start, i+1, (a, b) -> {
					return Integer.compare(a.y, b.y);
				});;
				start = i+1;
			}
			
		}
		
		if (start != n) {
			Arrays.sort(coordinateSet, start, n, (a, b) -> {
				return Integer.compare(a.y, b.y);
			});;
		}
		
		
		StringBuilder sb = new StringBuilder();
	
		for(int i=0; i<n; i++) {
			sb.append(coordinateSet[i].x).append(" ").append(coordinateSet[i].y).append("\n");
		}
		
		System.out.println(sb);
	}
}

 

• 입력으로 n개의 (x, y) 좌표를 받아 x 오름차순, x가 같다면 y 오름차순으로 정렬하는 문제.
• 정렬된 좌표를 출력하는 것이 목표.

 

 

 

---

1. 자료구조

• 배열 (Coordinate[] coordinateSet)
  • Coordinate 클래스 배열을 사용하여 좌표들을 저장함.
  • 좌표 정렬을 위해 Arrays.sort() 메서드를 사용.
• 문자열 빌더 (StringBuilder sb)
  • System.out.println()을 여러 번 호출하는 대신 StringBuilder를 사용하여 성능을 최적화.

 

 

 

---

2. 알고리즘 분석

 

1) 입력 및 객체 저장 (O(N))

• Scanner를 사용하여 n개의 (x, y) 좌표를 입력받아 배열 coordinateSet에 저장.
• 시간 복잡도: O(N)

 

2) 1차 정렬: x 좌표 기준 정렬 (O(N log N))

Arrays.sort(coordinateSet, (a, b) -> {
    return Integer.compare(a.x, b.x);
});

 

 

• Arrays.sort()를 사용하여 x 좌표를 기준으로 오름차순 정렬.
• 시간 복잡도: O(N log N) (퀵정렬 또는 병합정렬)

 

3) 2차 정렬: y 좌표 기준 정렬 (O(N log N))

int start = 0;
for (int i = 0; i < n - 1; i++) {
    if (coordinateSet[i].x != coordinateSet[i + 1].x) {
        Arrays.sort(coordinateSet, start, i + 1, (a, b) -> {
            return Integer.compare(a.y, b.y);
        });
        start = i + 1;
    }
}
if (start != n) {
    Arrays.sort(coordinateSet, start, n, (a, b) -> {
        return Integer.compare(a.y, b.y);
    });
}

 

 

• x가 동일한 구간에서 y 좌표를 기준으로 오름차순 정렬.
• Arrays.sort(coordinateSet, start, i + 1, ...)를 사용하여 x가 동일한 부분만 정렬.
• 전체적으로 O(N log N)

 

4) 출력 (O(N))

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append(coordinateSet[i].x).append(" ").append(coordinateSet[i].y).append("\n");
}
System.out.println(sb);

 

 

 

---

3. 전체 시간 복잡도

• 입력: O(N)
• 정렬(x 기준): O(N log N)
• 정렬(y 기준): O(N log N)
• 출력: O(N)
  ➡ 총 시간 복잡도: O(N log N)

 

 

 

---

4. 개선할 점

 

1) 이중 정렬을 하나의 정렬로 합칠 수 있음

Arrays.sort(coordinateSet, (a, b) -> {
    if (a.x == b.x) return Integer.compare(a.y, b.y);
    return Integer.compare(a.x, b.x);
});

 

 

• x가 같을 때 y를 비교하여 정렬을 한 번에 수행.
• 기존의 이중 정렬을 O(N log N)으로 최적화.

 

2) 좌표 클래스를 Comparable 인터페이스로 구현 가능

public static class Coordinate implements Comparable<Coordinate> {
    public int x, y;

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

    @Override
    public int compareTo(Coordinate other) {
        return (this.x == other.x) ? Integer.compare(this.y, other.y) : Integer.compare(this.x, other.x);
    }
}

 

 

Comparable을 구현하면 Arrays.sort(coordinateSet)만으로 정렬 가능.