[백준 알고리즘][자바] 11651번 : 좌표 정렬하기2

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

11651번: 좌표 정렬하기 2

이번 문제는 11650번 : 좌표 정렬하기에서는 x좌표를 첫 번째 기준 y좌표를 두 번째 기준으로 했다면,

반대로 y좌표가 첫 번째 기준 x좌표가 두번째 기준입니다.

2022.06.22 - [Algorithm/Baekjoon] - [백준 알고리즘][자바] 11650번 : 좌표 정렬하기

[백준 알고리즘][자바] 11650번 : 좌표 정렬하기

11650번과 매우 유사하기 때문에 특별한 과정은 생략하겠습니다.

 

 

풀이

2차원 배열을 사용하여 문제를 해결했지만, 11650번과 마찬가지로 x, y를 따로따로 해서 해결도 가능합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[][] xy = new int[N][2];
		
		for(int i = 0 ; i < N ; i++) {
			String[] xy_str = br.readLine().split(" ");
			
			xy[i][0] = Integer.parseInt(xy_str[0]);
			xy[i][1] = Integer.parseInt(xy_str[1]);
		}
		
		quickSort(xy, 0, N - 1);

		for(int i = 0 ; i < N ; i++) {
			bw.write(String.valueOf(xy[i][0]) + " " + String.valueOf(xy[i][1]) + "\n");
		}
	
		br.close();
		bw.flush();
		bw.close();
	}
	
	static void swap(int[][] a, int idx1, int idx2) {
		int temp = a[idx1][0];
		a[idx1][0] = a[idx2][0];
		a[idx2][0] = temp;
		
		temp = a[idx1][1];
		a[idx1][1] = a[idx2][1];
		a[idx2][1] = temp;
	}


	static void quickSort(int[][] data, int left, int right) {
		int pl = left;
		int pr = right;
		int pivot = data[(pl + pr) / 2][0]; // x좌표를 위한 피벗
		int pivot2 = data[(pl + pr) / 2][1]; // y좌표를 위한 피벗

		do {
			while (data[pl][1] < pivot2 || (data[pl][1] == pivot2 && data[pl][0] < pivot)) { // 만약 숫자가 같을 때 y좌표 기준으로 비교
				pl++;
			}
			while (data[pr][1] > pivot2 || (data[pr][1] == pivot2 && data[pr][0] > pivot)) { // 만약 숫자가 같을 때 y좌표 기준으로 비교
				pr--;
			}
			if (pl <= pr) {
				swap(data, pl, pr);
				pl++;
				pr--;
			}
		} while (pl <= pr);

		if (left < pr)
			quickSort(data, left, pr); 
		if (pl < right)
			quickSort(data, pl, right);
	}
	
	
}