글 읽기 - 11650번 좌표 정렬하기 문제

pscheol 5년 전 0

안녕하세요

제가 퀵정렬을 이용하여 정렬을 하고 있는데 직접 테스트를해보면 에러는 안나오는데

제출하면 틀렸습니다. 라고 나와서 찾다가 어디서 잘못 되었는지 알고싶어서 글을 남깁니다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		int a[][] = new int[n][2];
		for (int i = 0; i < n; i++) {
			a[i][0] = scan.nextInt();
			a[i][1] = scan.nextInt();
		}
		quickSort(a);
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i][0] + " " + a[i][1]);
		}
	}

	public static void quickSort(int[][] a) {
		qsort(a, 0, a.length - 1);
	}

	private static void qsort(int[][] a, int start, int end) {
		if (start < end) {
			int pivot = partision(a, start, end);
			qsort(a, start, pivot - 1);
			qsort(a, pivot + 1, end);
		}
	}

	private static int partision(int[][] a, int start, int end) {
		int left = start;
		int right = end + 1;
		int pivot = a[start][0];
		do {
			do {
				left++;
			} while (left <= end && a[left][0] < pivot);
			do {
				right--;
			} while (right >= start && a[right][0] > pivot);
			if (left < right) {
				swap(a, left, right);
			}
		} while (left < right);
		swap(a, start, right);
		return right;
	}

	private static void swap(int[][] a, int left, int right) {
		int tmp = a[left][0];
		if (a[left][0] == a[right][0]) {
			if (a[left][1] > a[right][1]) {
				tmp = a[left][1];
				a[left][1] = a[right][1];
				a[right][1] = tmp;
			}
		} else {
			a[left][0] = a[right][0];
			a[right][0] = tmp;
			tmp = a[left][1];
			a[left][1] = a[right][1];
			a[right][1] = tmp;
		}
	}
}

ho94949 5년 전 0

pivot을 잡을때 x좌표 값으로만 비교하는 이유가 무엇인가요?

pscheol 5년 전 0

문제에 x좌표가 증가하는 순이 첫번 째 기준이라 x 좌표 기준으로 pivot을 잡은 거고,

x좌표가 같을 때 y좌표를 비교하고 swap을 처리한거 입니다.

y값을 Pivot으로 하면 위 코드에서는 x값은 정렬은 안되겟죠.ㅠ

pscheol 5년 전 0

제가 문제를 잘못이해한걸가요..ㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11650번 좌표 정렬하기 문제

pscheol 5년 전 0

ho94949 5년 전 0

pscheol 5년 전 0

pscheol 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말