반응형
11650번: 좌표 정렬하기
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
www.acmicpc.net
1. 문제 추상화
X좌표와 Y좌표가 주어질 때, X좌표의 내림차순으로 정렬하라. X좌표가 같으면 Y좌표의 내림차순으로 정렬하라.
2. 알고리즘
1. X좌표와 Y좌표를 저장할 수 있는 이차원 배열을 생성한다.
2. X좌표의 내림차순으로 비교하다가 X좌표가 같은 경우 Y좌표의 내림차순으로 비교하는 조건을 분기한다.
퀵정렬, 병합정렬, 힙정렬을 사용하였다. 버블정렬은 시간초과가 나고 카운팅정렬은 메모리초과가 났다.
3. 코드
퀵정렬 ( Quick Sort )
public static void doQuickSort(int left, int right) {
int leftPointer = left;
int rightPointer = right;
int pivotX = arr[(left+right)/2][0];
int pivotY = arr[(left+right)/2][1];
do {
while(arr[leftPointer][0] <= pivotX ) {
if(arr[leftPointer][0] == pivotX) { // 좌표의 X가 같은 경우
if(arr[leftPointer][1] < pivotY) leftPointer++;
else break;
}else {
leftPointer++;
}
}
while(arr[rightPointer][0] >= pivotX ) {
if(arr[rightPointer][0] == pivotX) { // 좌표의 X가 같은 경우
if(arr[rightPointer][1] > pivotY) rightPointer--;
else break;
}else {
rightPointer--;
}
}
if(leftPointer <= rightPointer) {
swap(leftPointer++, rightPointer--);
}
}while(leftPointer <= rightPointer);
//재귀함수
if(left < rightPointer) doQuickSort(left,rightPointer);
if(leftPointer < right) doQuickSort(leftPointer,right);
}
public static void swap(int leftPointer, int rightPointer) {
int tmpX = arr[leftPointer][0];
int tmpY = arr[leftPointer][1];
arr[leftPointer][0] = arr[rightPointer][0];
arr[leftPointer][1] = arr[rightPointer][1];
arr[rightPointer][0] = tmpX;
arr[rightPointer][1] = tmpY;
}
병합정렬 (Merge Sort)
public static void doMergeSort(int left, int right) {
if(left < right) {
int center = ( left + right) / 2;
doMergeSort(left,center);
doMergeSort(center+1,right);
applyMerge(left,right);
}
}
public static void applyMerge(int left, int right) {
int[][] leftArr = new int[right-left+1][2];
int center = (left + right)/2;
int leftPointer = 0;
int rightPointer = center+1;
int arrPointer = left;
int leftArrSize = 0;
for(int i=left; i<=center;i++) {
leftArr[leftArrSize][0] = arr[i][0];
leftArr[leftArrSize++][1] = arr[i][1];
}
for(arrPointer = left; arrPointer <= right; arrPointer++) {
if(leftPointer < leftArrSize && rightPointer <= right) {
if(leftArr[leftPointer][0] < arr[rightPointer][0]) {
arr[arrPointer][0] = leftArr[leftPointer][0];
arr[arrPointer][1] = leftArr[leftPointer++][1];
}
else if(leftArr[leftPointer][0] == arr[rightPointer][0]) { //X좌표가 같은경우
if(leftArr[leftPointer][1] < arr[rightPointer][1]) {
arr[arrPointer][0] = leftArr[leftPointer][0];
arr[arrPointer][1] = leftArr[leftPointer++][1];
}else {
arr[arrPointer][0] = arr[rightPointer][0];
arr[arrPointer][1] = arr[rightPointer++][1];
}
}else {
arr[arrPointer][0] = arr[rightPointer][0];
arr[arrPointer][1] = arr[rightPointer++][1];
}
}else {
break;
}
}
while(leftPointer < leftArrSize) {
arr[arrPointer][0] = leftArr[leftPointer][0];
arr[arrPointer++][1] = leftArr[leftPointer++][1];
}
}
힙정렬 ( Heap Sort )
public static void doHeapSort() {
int lastChildIndex = arr.length - 1;
int lastParentIndex = ( lastChildIndex - 1 )/2;
for(int i = lastParentIndex; i >= 0; i--) {
makeHeap(i,lastChildIndex);
}
for(int i = arr.length-1; i > 0; i--) {
swap(0,i);
makeHeap(0,i-1);
}
}
public static void makeHeap(int pivotIndex, int lastChildIndex) {
int pivotX = arr[pivotIndex][0];
int pivotY = arr[pivotIndex][1];
int childIndex = 0;
int parentIndex = 0;
for(parentIndex = pivotIndex; parentIndex < (lastChildIndex + 1)/2; parentIndex = childIndex) {
int leftChildIndex = 2*parentIndex + 1;
int rightChildIndex = leftChildIndex + 1;
if(rightChildIndex > lastChildIndex) childIndex = leftChildIndex;
else {
if(arr[leftChildIndex][0] > arr[rightChildIndex][0]) childIndex = leftChildIndex;
else if(arr[leftChildIndex][0] == arr[rightChildIndex][0]) { //X좌표가 같은 경우
childIndex = arr[leftChildIndex][1] > arr[rightChildIndex][1] ? leftChildIndex : rightChildIndex;
}
else childIndex = rightChildIndex;
}
if(pivotX > arr[childIndex][0]) break;
else if(arr[childIndex][0] == pivotX ) {
if( pivotY > arr[childIndex][1]) break;
}
arr[parentIndex][0] = arr[childIndex][0];
arr[parentIndex][1] = arr[childIndex][1];
}
arr[parentIndex][0] = pivotX;
arr[parentIndex][1] = pivotY;
}
전체 코드 ( 힙 정렬 기준 )
package boj11650;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main4 {
private static BufferedReader br;
private static BufferedWriter bw;
private static StringBuilder sb;
private static StringTokenizer stz;
private static int[][] arr;
public static void main(String[] args) throws NumberFormatException, IOException {
createObjects();
createArr();
initializeArr();
doHeapSort();
printArr();
closeIO();
}
public static void createObjects() {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
sb = new StringBuilder();
}
public static void createArr() throws NumberFormatException, IOException {
int size = Integer.parseInt(br.readLine());
arr = new int[size][2];
}
public static void initializeArr() throws IOException {
for(int i=0; i<arr.length;i++) {
stz = new StringTokenizer(br.readLine()," ");
arr[i][0] = Integer.parseInt(stz.nextToken());
arr[i][1] = Integer.parseInt(stz.nextToken());
}
}
public static void doHeapSort() {
int lastChildIndex = arr.length - 1;
int lastParentIndex = ( lastChildIndex - 1 )/2;
for(int i = lastParentIndex; i >= 0; i--) {
makeHeap(i,lastChildIndex);
}
for(int i = arr.length-1; i > 0; i--) {
swap(0,i);
makeHeap(0,i-1);
}
}
public static void makeHeap(int pivotIndex, int lastChildIndex) {
int pivotX = arr[pivotIndex][0];
int pivotY = arr[pivotIndex][1];
int childIndex = 0;
int parentIndex = 0;
for(parentIndex = pivotIndex; parentIndex < (lastChildIndex + 1)/2; parentIndex = childIndex) {
int leftChildIndex = 2*parentIndex + 1;
int rightChildIndex = leftChildIndex + 1;
if(rightChildIndex > lastChildIndex) childIndex = leftChildIndex;
else {
if(arr[leftChildIndex][0] > arr[rightChildIndex][0]) childIndex = leftChildIndex;
else if(arr[leftChildIndex][0] == arr[rightChildIndex][0]) {
childIndex = arr[leftChildIndex][1] > arr[rightChildIndex][1] ? leftChildIndex : rightChildIndex;
}
else childIndex = rightChildIndex;
}
if(pivotX > arr[childIndex][0]) break;
else if(arr[childIndex][0] == pivotX ) {
if( pivotY > arr[childIndex][1]) break;
}
arr[parentIndex][0] = arr[childIndex][0];
arr[parentIndex][1] = arr[childIndex][1];
}
arr[parentIndex][0] = pivotX;
arr[parentIndex][1] = pivotY;
}
public static void swap(int root, int index) {
int tmpX = arr[root][0];
int tmpY = arr[root][1];
arr[root][0] = arr[index][0];
arr[root][1] = arr[index][1];
arr[index][0] = tmpX;
arr[index][1] = tmpY;
}
public static void printArr() throws IOException {
for(int i =0; i < arr.length; i++) {
sb.append(arr[i][0]+" "+arr[i][1]).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
public static void closeIO() throws IOException {
br.close();
bw.close();
}
}
반응형
'문제풀이 > Sorting' 카테고리의 다른 글
| [python] 백준 2750번 수 정렬하기1 : 버블 정렬(BubbleSort) 향상시키기 (0) | 2023.04.05 |
|---|---|
| [JAVA] 백준 10814번 나이순 정렬 : 단어정렬 (0) | 2021.09.07 |
| [JAVA] 백준 1427번 소트인사이드 : 내림차순 정렬 (0) | 2021.08.10 |
| [JAVA] 백준 2108번 통계학 : 정렬 (0) | 2021.08.09 |
| [JAVA] 백준 10989번 수 정렬하기 3 : 카운팅 정렬 (Counting Sort) (0) | 2021.08.05 |