백준/11650번/Java - 좌표 정렬하기

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

11650번: 좌표 정렬하기

---

퀵정렬에 대해 공부하던 중, 이 문제를 발견하여 퀵정렬을 활용해 문제를 풀어보았다.

퀵정렬에 대한 내용은 아래와 같다.

참고한 영상

퀵 정렬이란 pivot을 기준으로 pivot의 왼쪽에는 pivot보다 작은 값을, 오른쪽에는 큰 값을 위치시켜가면서 배열을 정렬하는 방법이다.

여러 설명들을 찾아봤는데 위의 영상이 이해하는데 가장 큰 도움이 되었다.

파티션내에서 start 포인터와 end 포인터를 움직여가며 pivot을 기준으로 값을 정렬하고 정렬이 종료되면 종료 시점의 start 포인터 위치를 기준으로 다시 파티션을 분할하여 각 파티션에서 정렬을 재귀적으로 수행하는 방식이다.

아래 코드는 위 영상의 설명대로 퀵 정렬 코드를 작성한 것이다.

import java.io.*;
import java.util.Scanner;

public class Main {

    static int[] arr;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        arr = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
        }
        int start = 0, end = N-1;
        quickSort(start, end);
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void quickSort(int start, int end) {
        int part = partition(start, end); //part는 정렬 후 우측 파티션의 가장 첫번째 값.
        if(start < part - 1) {
            //start < part - 1인 경우는 좌측 파티션에 원소가 1개 뿐이므로 더 이상 정렬할 필요 없음.
            quickSort(start, part - 1);
        }
        if(part < end) {
            // part가 end와 같거나 배열 인덱스를 벗어나면 더이상 우측 파티션 정렬할 필요 없음
            quickSort(part, end);
        }
    }
    //배열을 두 피벗을 기준으로 두 파티션으로 나눈다.
    private static int partition(int start, int end) {
        int pivot = arr[(start + end) / 2];//배열의 가운데 위치한 값을 피벗으로 지정한다.
        while(start <= end) { // end 포인터가 start 포인터가 서로 지나치기 전까지 반복한다.
            while(arr[start] < pivot) start++; // 피벗의 왼쪽에 피벗보다 큰값을 찾아야 하므로 피벗보다 작은 경우 포인터는 그냥 지나가면 된다.
            while (arr[end] > pivot) end--; // 오른쪽은 반대의 경우.
            //start 포인터는 피벗보다 큰 값을, end 포인터는 작은 값을 찾았을 때, 서로 지나치지 않았다면 값을 swap한다.
            if(start <= end) {
                swap(start, end);
                start++;
                end--;
            }
        }
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        //start > end가 되어 while문이 종료된 경우는 start 포인터가 end 포인터를 지나치게 된 경우이다.
        //이 경우 배열을 둘로 나누는 파티셔닝이 종료되고 start 포인터의 위치가 우측 파티션의 첫번째 위치이다.
        return start;
    }

    private static void swap(int start, int end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
}
/**
 * 입력
 * 42 32 24 60 15 5 90 45
 *
 * 5 3 2 1 4
 */

 

문제 역시 단순하게 정렬만 하면 되는 문제이므로 그대로 퀵정렬을 사용하면 된다.

문제에서는 x좌표와 y좌표를 갖는 점을 정렬하는 것이므로 배열의 원소로 사용할 클래스를 선언하였다.

Dot 클래스는 x좌표를 먼저, 그 다음 y 좌표를 비교하여 대소관계를 정하기 때문에 pivot 값과 비교할 메서드를 구현하였다.

 

import java.io.*;
import java.util.StringTokenizer;
class Dot {
    int x;
    int y;
    public Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean isBigger(Dot pivot) {
        if(this.x > pivot.x) return true;
        else if(this.x < pivot.x) return false;
        else {
            if(this.y > pivot.y) return true;
            else return false;
        }
    }
    public boolean isSmaller(Dot pivot) {
        if(this.x < pivot.x) return true;
        else if(this.x > pivot.x) return false;
        else {
            if(this.y < pivot.y) return true;
            else return false;
        }
    }
}

public class Main {

    static Dot[] arr;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new Dot[N];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[i] = new Dot(x, y);
        }
        int start = 0, end = N - 1;
        quickSort(start, end);
        for(int i=0; i<N; i++) {
            bw.write(arr[i].x + " " + arr[i].y+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    private static void quickSort(int start, int end) {
        int part = partition(start, end);
        if(start < part - 1) {
            quickSort(start , part -1);
        }
        if(part < end) {
            quickSort(part, end);
        }
    }

    private static int partition(int start, int end) {
        int pivotX = arr[(start+end)/2].x;
        int pivotY = arr[(start+end)/2].y;
        Dot pivot = new Dot(pivotX, pivotY);
        while(start <= end) {
            while(arr[start].isSmaller(pivot)) {
                start++;
            }
            while(arr[end].isBigger(pivot)) {
                end--;
            }
            if(start <= end) {
                swap(start, end);
                start++;
                end--;
            }
        }
        return start;
    }

    private static void swap(int start, int end) {
        int sx = arr[start].x;
        int sy = arr[start].y;
        int ex = arr[end].x;
        int ey = arr[end].y;
        arr[start] = new Dot(ex, ey);
        arr[end] = new Dot(sx, sy);
    }
}