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

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

11650번: 좌표 정렬하기

이번 문제는 좌표를 사용하여 첫 번째는 x좌표 기준으로 오름차순으로 정렬하고, 같은 숫자가 존재할 때 y좌표 기준으로 오름차순을 하는 문제입니다.

 

여러 가지 정렬 알고리즘에다가 x좌표가 같은 숫자일 때 y좌표 기준으로 정렬하는 부분을 추가해주면 해결할 수 있습니다.

다만 제한시간이 1초이기 때문에 시간 복잡도가 중요합니다.

 

우선, 단순 삽입 정렬과 버블 정렬의 알고리즘을  x좌표가 같을 때 y좌표 기준으로 오름차순 하도록 수정하였더니 시간 초과가 발생하였습니다.

 

그다음은 먼저 퀵 정렬로 x좌표 기준으로 정렬 한 다음 버블 정렬을 사용하여 x좌표가 같은 것들만 y좌표 기준으로 재정렬을 하였는데 진행률이 80%까지 갔다가 시간 초과가 발생하였습니다. 아마도 숫자의 개수와 범위가 커지면서 시간 초과가 발생하는 거 같습니다. (관련 소스는 제일 아래쪽에 있습니다.)

 

마지막으로 결국 퀵 정렬을 y좌표까지 고려하도록 수정한 다음 퀵정렬만을 사용하여 문제를 해결하였습니다.

2022.01.01 - [Algorithm/Theory] - [자바] 가장 빠른 정렬 알고리즘 - 퀵 정렬 (Quick Sort)

[자바] 가장 빠른 정렬 알고리즘 - 퀵 정렬 (Quick Sort)

풀이

1. 퀵정렬 - 초기 버전

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[] x = new int[N];
		int[] y = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			String[] xy = br.readLine().split(" ");
			
			x[i] = Integer.parseInt(xy[0]);
			y[i] = Integer.parseInt(xy[1]);
		}
		
		quickSort(x, y, 0, N - 1);

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


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

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

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

 

퀵 정렬을 사용하여 문제를 해결하고 다른 분은 어떻게 풀었나 확인했었는데, Arrays.sort()를 사용하는 방법이 있었습니다.

풀이 방법에 xy좌표를 2차원 배열로 푸는 것을 보고 2차원 배열 퀵 정렬로 수정해보았습니다.

 

2. 퀵 정렬 - 2차원 배열 버전

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];
		int pivot2 = data[(pl + pr) / 2][1]; // y좌표를 위한 피벗

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

 

아래에서부터

1. 초기 버전
2. 2차원 배열 버전

입니다. 2차원을 탐색해야해서 그런지 시간을 오래 걸리지만 코드 길이는 줄어들었습니다.

 

시간 초과 버전들

1. 단순 선택 정렬 사용 - 시간 초과

2022.01.22 - [Algorithm/Theory] - [자바] 단순 선택 정렬과 단순 삽입 정렬

[자바] 단순 선택 정렬과 단순 삽입 정렬

단순 선택 정렬 알고리즘을 사용하여 제출을 해보았지만, 시간 초과가 되었습니다.

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[] x = new int[N];
		int[] y = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			String[] xy = br.readLine().split(" ");
			
			x[i] = Integer.parseInt(xy[0]);
			y[i] = Integer.parseInt(xy[1]);
		}
		
		for(int i = 0 ; i < N - 1 ; i++) {
			int min = i;
			for(int j = i + 1 ; j < N ; j++) {
				if(x[j] < x[min]) {
					min = j;
				}else if(x[j] == x[min]) {
					if(y[j] < y[min]) {
						min = j;
					}
				}
			}
			swap(x, i, min);
			swap(y, i, min);
		}

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

 

2. 버블 정렬 - 시간 초과

단순 삽입 정렬과 버블 정렬 모두 최악의 시간 복잡도는 O(n^2)로 동일하지만, 버블 정렬이 미세하게나마 최적화가 되어있어서 한번 시도해보았습니다. 하지만 역시 시간 초과였습니다. 

2022.01.21 - [Algorithm/Theory] - [자바] 버블 정렬(Bubble Sort)

[자바] 버블 정렬(Bubble Sort)

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[] x = new int[N];
		int[] y = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			String[] xy = br.readLine().split(" ");
			
			x[i] = Integer.parseInt(xy[0]);
			y[i] = Integer.parseInt(xy[1]);
		}
		
		// 버블 정렬
		for (int i = 0; i < N - 1; i++) { // 배열의 크기 N - 1 만큼 패스 작업
			int check = 0;
			for (int j = N - 1; j > i; j--) { // 배열의 끝 n-1 부터 비교
				if (x[j - 1] > x[j]) { // 대소비교
					swap(x, j - 1, j); // 교환
					check++;
				}else if(x[j - 1] == x[j]) {
					if(y[j - 1] > y[j]) {
						swap(x, j - 1, j); // 교환
						check++;
					}
				}
			}
			if (check == 0) { // 교환 횟수가 0번이라면 반복문을 빠져나감
				break;
			}
		}

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

 

3. 퀵정렬 + 버블 정렬

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[] x = new int[N];
		int[] y = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			String[] xy = br.readLine().split(" ");
			
			x[i] = Integer.parseInt(xy[0]);
			y[i] = Integer.parseInt(xy[1]);
		}
		
		quickSort(x, y, 0, N - 1);
		
		// 버블 정렬
		for (int i = 0; i < N - 1; i++) {
			int check = 0;
			for (int j = N - 1; j > i; j--) {
				if(x[j - 1] == x[j]) {
					if(y[j - 1] > y[j]) {
						swap(x, j - 1, j); // 교환
						swap(y, j - 1, j); // 교환
						check++;
					}
				}
			}
			if (check == 0) {
				break;
			}
		}

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


	static void quickSort(int[] data, int[] data2, int left, int right) {
		int pl = left;
		int pr = right;
		int pivot = data[(pl + pr) / 2];

		do {
			while (data[pl] < pivot) {
				pl++;
			}
			while (data[pr] > pivot) {
				pr--;
			}
			if (pl <= pr) {
				swap(data, pl, pr);
				swap(data2, pl, pr);
				pl++;
				pr--;
			}
		} while (pl <= pr);

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