[백준/JAVA] 11650번 좌표 정렬하기

• 좌표를 정렬하는 문제
  https://www.acmicpc.net/problem/11650

1. 문제

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

2. 문제 접근

1) 점의 개수 N을 입력받는다.
2) N만큼 좌표를 입력받는다.
3) 두가지 방법으로 정렬을 해볼 예정이다.
3-1) 병합정렬을 진행하되 병합과정에서 병합하려는 두 배열의 X좌표를 먼저 비교하고 만약 같을 시 Y좌표를 비교하는 방법을 사용한다.
3-2) X좌표와 Y좌표를 입력받을 때, X좌표와 Y좌표의 가중치를 다르게 하여 저장한다.
-X좌표는 일반적인 정수로, Y좌표는 소수로 변환하여 두 개를 더하여 저장!

3. 코드

1) 병합정렬 시 X좌표와 Y좌표를 같이 비교

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;

public class Main {

    static int data[][];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int num[][] = new int[N][2];
        data = new int[N][2];

        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            num[i][0] = Integer.parseInt(st.nextToken());
            num[i][1] = Integer.parseInt(st.nextToken()); 
        }

        MergeSort(num,0,N-1);

        for(int i=0;i<N;i++) {
            sb.append(num[i][0] + " " + num[i][1]).append("\n");
        }

        System.out.print(sb);
    }


    static void MergeSort(int num[][], int start, int end) {

        if(start>=end) {
            return;
        }

        int mid = (start+end)/2;
        MergeSort(num, start, mid);
        MergeSort(num, mid+1, end);
        Merge(num, start, mid, end);
    }

    static void Merge(int num[][], int start, int mid, int end) {
        int i = start;
        int j = mid+1;
        int k = start;

        while(i<=mid && j<=end) {
            if(num[i][0]<num[j][0]) {
                data[k][0] = num[i][0];
                data[k][1] = num[i][1];
                i++;
            }
            else if(num[i][0]> num[j][0]) {
                data[k][0] = num[j][0];
                data[k][1] = num[j][1];
                j++;
            }
            else {
                if(num[i][1] > num[j][1]) {
                    data[k][0] = num[j][0];
                    data[k][1] = num[j][1];
                    j++;
                }
                else {
                    data[k][0] = num[i][0];
                    data[k][1] = num[i][1];
                    i++;
                }
            }
            k++;
        }
        if(i>mid) {
            for(int t=j;t<=end;t++) {
                data[k][0]= num[t][0];
                data[k][1]= num[t][1];
                k++;
            }
        }
        else {
            for(int t=i;t<=mid;t++) {
                data[k][0]= num[t][0];
                data[k][1]= num[t][1];
                k++;
            }
        }

        for(int t=start;t<=end;t++) {
            num[t][0]= data[t][0];
            num[t][1]= data[t][1];
        }
    }
}

2) 가중치를 다르게 하여 저장

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static double[] temp = new double[100000];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        double [] arr = new double[size];
        StringTokenizer st;
        for(int i=0; i<arr.length; i++) {
            st = new StringTokenizer(br.readLine());
            double num = Double.parseDouble(st.nextToken());
            if(num>=0)
                arr[i]= num + (Double.parseDouble(st.nextToken())+100000)/1000000;
            else {
                arr[i] = num - ((-1) * Double.parseDouble(st.nextToken())+100000)/1000000;
            }
        }
        br.close();
        StringBuilder sb = new StringBuilder();
        merge_sort(arr, 0, size-1);
        for(int i=0;i<arr.length;i++) {
            if(arr[i]>=0) {
                sb.append((int)arr[i]).append(' ').append(Math.round(((arr[i]-(int)arr[i])-0.1)*1000000)).append('\n');
            }
            else {
                sb.append((int)arr[i]).append(' ').append(Math.round(((arr[i]-(int)arr[i])+0.1)*1000000)).append('\n');
            }
        }
        System.out.print(sb);
    }

    private static void merge_sort(double [] arr, int start, int last) {
        int mid;

        if(start<last) {
            mid = (start+last)/2;
            merge_sort(arr, start, mid);
            merge_sort(arr, mid+1, last);
            merge(arr, start, mid, last);
        }
    }

    private static void merge(double [] arr, int start, int mid, int last) {
        int index = start;
        int i1 = start;
        int i2 = mid+1;

        while(i1<=mid && i2<=last) {
            if(arr[i1] < arr[i2]) {
                temp[index++] = arr[i1++];
            }
            else {
                temp[index++] = arr[i2++];
            }
        }

        if(i1>mid) {
            for(int i = i2; i<=last;i++) {
                temp[index++] = arr[i];
            }
        }
        else {
            for(int i = i1; i<=mid;i++) {
                temp[index++] = arr[i];
            }
        }

        for(int i=start; i<=last;i++) {
            arr[i] = temp[i];
        }
    }
}