[백준] 11650번 : 좌표 정렬하기- JAVA[자바] - 정렬 - 티스토리

오늘의 토픽 : Sort && Comparator , Comparable

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

11650번: 좌표 정렬하기

*별표표시는 저의 생각이고, 나머지는 문제를 인용했습니다.

 

고찰 

 * 일단 Comparator 사용법에 대해 어느 정도 숙지하였다. 하지만 완벽하지 않다. 제네릭스에 넣어야 하는게 햇갈린다. 

 * 배열을 비교할 것이라서 Wrapper클래스를 사용하지 않아도 된다. 

Arrays.sort의 경우, primitive 타입과 Object 둘 다 정렬에 이용할 수 있다. 

만약, 컬렉션이였다면, int말고 Integer를 사용했어야할 것이다.

  

 부족한 점 

 * 여기서 내가 시간복잡도를 왜 따져야하는지 모르고있다.

 * 주어지는 N의 갯수는 10만개이다.

 * 만약 연산이 N^2이 되는 정렬을 수행한다면  10만 x 10만 .. 시간이 엄청 오래걸린다 

 * N^2인 정렬이 뭐가있지 ?  ->선택정렬 

 * N^2보다 적은 시간복잡도의 정렬이 뭐가있지? -> 퀵정렬, 병합정렬

접근 방식

(Comparator와 Comparable에 익숙해지기 위해 일부러 따로따로 풀이를 해보았다.)

1. 2차원 배열로 x좌표와 y좌표를 받는다. 그리고 Comparator를 이용해서 정렬을 커스텀해서 푼다. 
2. Point라는 class를 따로 만든다. (멤버변수는 2가지 x,y ) 그리고 Comparable을 implements해서 마찬가지로 커스텀한다. 
다른 분들의 풀이를 보니 merge sort, quick sort를 이용해서 풀었다. 직접구현해서 사용할 정도로 정렬에 더 익숙해져야겠다.

 

접근방식 1

/* 작성 : 21.07.06 
 * 고찰 
 * 일단 Comparator 사용법에 대해 어느 정도 숙지하였다. 하지만 제네릭스에 넣어야 하는게 햇갈린다. 
 * 배열을 비교할 것이라서 Wrapper클래스를 사용하지 않아도 되는 것 같다. 
 * 
 * 부족한 점 
 * 여기서 내가 시간복잡도를 왜 따져야하는지 모르고있다.
 * 주어지는 N의 갯수는 10만개이다.
 * 만약 연산이 N^2이 되는 정렬을 수행한다면 시간이 엄청 오래걸린다 
 * N^2인 정렬이 뭐가있지 ? 
 * ->선택정렬 
 *   
 */
package sort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class BOJ_11650_Comparator {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		
		int [][] xy = new int [n][2];
		
		for(int i=0 ; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			xy[i][0] = x;
			xy[i][1] = y;
		}
		
		Arrays.sort(xy,new Comparator<int[]>(){
			public int compare(int[] o1, int[]o2) {
				if(o1[0]==o2[0])
					return o1[1]-o2[1];
				else
					return o1[0]-o2[0];
			}
		});
		for(int[] list : xy) {
			bw.write(list[0]+" "+list[1]);
			bw.write("\n");
		}
		bw.flush();
		bw.close();
		br.close();
		
			
		
	}

}

접근방식 2

/*
 * Point 클래스를 import하지 않고 comparable을 implement해서 사용하려고 한다.
 */
package sort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_11650_Comparable {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		Point[] p = new Point[n];
		
		
		
		for(int i=0 ; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());			
			p[i] = new Point(x,y);
		}
		
		Arrays.sort(p);
		for(Point list : p) {
			sb.append(list.x).append(" ").append(list.y).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();

	}

}

class Point implements Comparable<Point>{
	int x;
	int y;
	public Point(int x,int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Point o) {
		if(this.x == o.x)
			return this.y - o.y;
		else
			return this.x - o.x;
	}
}

자유로운 코멘트 환영합니다.

부족한 점이 보인다면 바로 지적해주시면 감사하겠습니다.

더욱 더 성장하겠습니다.
읽어주셔서 감사합니다.