[백준] 11650번 : 좌표 정렬하기(JAVA)

투다다다ㅏ다닥.gif

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

11650번: 좌표 정렬하기

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 12단계

 

정렬의 카테고리에 포함되어 있는 문제이다.

 

시간제한은 1초인데 좌표의 개수는 최대 10만개이니 시간복잡도가

 

O(NlogN)인 정렬방법으로 풀어야한다.

 

나는 자바 라이브러리에 포함된 정렬이 아닌 따로 합병정렬 클래스를

 

선언하여 만들었다.

 

4번의 도전끝에 성공하였는데 먼저 첫번 째로 올린 코드이다.

 

import java.util.Scanner;

class Coordinate {
	public int X;
	public int Y;
	
	public Coordinate(int X, int Y) {
		this.X = X;
		this.Y = Y;
	}
	
	public void Print() {
		System.out.println(X + " " + Y);
	}
}

class MergeSort {
	public void Merge_Sort(Coordinate[] x, int left, int right) {
		int mid;
		if(left < right) {
			mid = (left + right) / 2;
			Merge_Sort(x, left, mid);
			Merge_Sort(x, mid + 1, right);
			Merge(x, left, mid, right);
		}
	}
	
	public void Merge(Coordinate[] x, int left, int mid, int right) {
		int i = left;
		int j = mid + 1;
		int k = left;
		Coordinate[] temp = new Coordinate[x.length];
		
		while(i <= mid && j <= right) {
			if(x[i].X < x[j].X) {
				temp[k++] = x[i++];
			} else if ( x[i].X == x[j].X) {
				if(x[i].Y < x[j].Y) {
					temp[k++] = x[i++];
				} else {
					temp[k++] = x[j++];
				}
			} else {
				temp[k++] = x[j++];
			}
		}
		
		while(i <= mid)
			temp[k++] = x[i++];
		
		while(j <= right)
			temp[k++] = x[j++];
		
		for(int index = left; index < k; index++)
			x[index] = temp[index];
	}
	
}

public class Question_11650 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		Coordinate[] cor = new Coordinate[N];
		
		for(int i = 0; i < N; i++) {
			int X = sc.nextInt();
			int Y = sc.nextInt();
			cor[i] = new Coordinate(X, Y);
		}
		
		MergeSort MS = new MergeSort();
		
		MS.Merge_Sort(cor, 0, cor.length - 1);
		
		for(int i = 0; i < N; i++) {
			cor[i].Print();
		}
	
	}

}

 

시간초과가 나버린 코드이다.

 

첫번 째로 가장큰 문제점은 합병정렬 과정 중에서

 

합병할 때 마다 배열을 선언하는 것이 가장 큰 문제가 아닌가 싶다.

 

이 문제를 4번째로 정답을 제출할 때 알아차려 3번의 실패를 했다.

 

두번 째로 느린 입력의 방식인 Scanner의 방식을 사용했다고 생각해서

 

2번째, 3번째 제출할 때 Buffer의 방식으로 바꾸어 사용했다.

 

import java.io.*;

class Coordinate {
	public int X;
	public int Y;
	
	public Coordinate(int X, int Y) {
		this.X = X;
		this.Y = Y;
	}
	
}

class MergeSort {
	Coordinate[] temp;
	
	public void Input(int n) {
		temp = new Coordinate[n];	
	}

	public void Merge_Sort(Coordinate[] x, int left, int right) {
		int mid;
		if(left < right) {
			mid = (left + right) / 2;
			Merge_Sort(x, left, mid);
			Merge_Sort(x, mid + 1, right);
			Merge(x, left, mid, right);
		}
	}
	
	public void Merge(Coordinate[] x, int left, int mid, int right) {
		int i = left;
		int j = mid + 1;
		int k = left;
		
		while(i <= mid && j <= right) {
			if(x[i].X < x[j].X) {
				temp[k++] = x[i++];
			} else if ( x[i].X == x[j].X) {
				if(x[i].Y < x[j].Y) {
					temp[k++] = x[i++];
				} else {
					temp[k++] = x[j++];
				}
			} else {
				temp[k++] = x[j++];
			}
		}
		
		while(i <= mid)
			temp[k++] = x[i++];
		
		while(j <= right)
			temp[k++] = x[j++];
		
		for(int index = left; index < k; index++)
			x[index] = temp[index];
	}
	
}

public class Question_11650 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		Coordinate[] cor = new Coordinate[N];
		
		for(int i = 0; i < N; i++) {
			String Input = br.readLine();
			
			String[] Split = Input.split(" ");
			
			int X = Integer.parseInt(Split[0]);
			int Y = Integer.parseInt(Split[1]);
			
			cor[i] = new Coordinate(X, Y);
		}
		
		MergeSort MS = new MergeSort();
		
		MS.Input(cor.length);
		
		MS.Merge_Sort(cor, 0, cor.length - 1);
		
		for(int i = 0; i < N; i++)
			System.out.println(cor[i].X + " " + cor[i].Y);
		
	}

}

 

마지막으로 정답을 얻은 코드이며,

 

합병정렬의 클래스 처음 부분에 임시로 쓸 배열을 한 번만 선언했다.

 

입력도 Buffer의 방식으로 받아주었다.

 

정렬의 문제마다 합병 정렬의 작동 방식과 연습을 하려고 계속 사용 중 인데

 

같은 시간복잡도를 가지는 힙 정렬도 연습을 해봐야겠다.