[정렬] 백준 - 좌표 정렬하기

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

11650번: 좌표 정렬하기

 

-문제해설

x좌표의 오름차순으로 정렬하는데 x좌표가 같은 경우에는 y좌표 오름차순으로 정렬하는 문제이다.

맨 처음 Arrays.sort써도 될까 싶었는데 다행히 통과됐다.

 

Arrays.sort의 익명함수를 사용해서 풀었다.

 

파이썬에서는 x좌표를 리스트의 인덱스, y좌표를 해당 인덱스의 값으로해서 풀었다.

이때 x좌표가 -100,000 ~ 100,000이므로 리스트를 처음에 생성할 때 크기를 200,001로 지정한다.

그리고 100,000 인덱스가 좌표 0이라고 가정한다.

예를 들어서 x가 5이면 리스트의 인덱스는 100,005이고, x가 -10이면 리스트의 인덱스는 99,995이다.

 

파이썬도 자바 익명함수처럼 lambda식을 이용해서 sort함수를 사용자 입맛에 맞게 정의해서 정렬할 수 있다.

 

 

-자바

package sort;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class BJ11650 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		StringTokenizer st;
		
		//point라는 객체는 int x, int y를 필드로 가지는 클래스이다. 이를 활용한다.
		//사용자 객체를 만들어도 되지만 귀찮으니깐 ㅎ
		Point[] arr = new Point[n];
		
		for( int i=0; i<n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			
			//Point객체의 생성자 형식에 맞게 new Point( x, y ) 형식으로 데이터를 집어넣는다.
			arr[i] = new Point( Integer.parseInt( st.nextToken() ), Integer.parseInt( st.nextToken() ) );
		}
		
		//이제 arr배열을 x좌표 오름차순으로 정렬하되 x좌표가 같을 경우 y좌표를 오름차순으로 정렬하기 위해
		//Arrays.sort 메소드에 Comparator 인터페이스의 compare메소드를 재정의해서 
		//조건에 맞도록 정렬한다.
		Arrays.sort( arr, new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				if( o1.x==o2.x ) return o1.y - o2.y;
				else return o1.x - o2.x;
			}
		});
		
		//출력속도를 향상시키기 위해 StringBuffer에 출력값을 모두 저장했다가
		//한꺼번에 출력한다.
		StringBuffer sb = new StringBuffer();
		for( int i=0; i<n; i++ ) sb.append( arr[i].x + " " + arr[i].y + "\n" );
		System.out.println( sb );
	}
}

 

 

-파이썬

import sys
readline = sys.stdin.readline
n = int( readline() )

#x좌표가-100000 ~ 1000000 이므로 -100000일때는 100000-100000=0인덱스
#x가 100000일 때는 100000+100000 = 200000 인덱스가 되도록
#arr배열의 크기를 200000으로 설정한다.
arr = [ [] for _ in range(200001) ]
for _ in range(n):
    a, b = map( int, readline().split() )
    
    #배열의 100000인덱스가 좌표값 0이라고 가정한다.
    #이를 위해서 x좌표값에 100000을 더하고 이를 인덱스로 사용한다.
    #x좌표 인덱스 배열에 b값을 추가시킨다.
    arr[100000 + a].append( b )

#arr크기인 200001까지 순회
for i in range(len(arr)):
    #0이 아닌경우에는 i인덱스 배열에 값이 존재한다는 거니깐
    if len(arr[i]) != 0:    
        arr[i].sort()   #y좌표값을 오름차순으로 정렬
        for j in range(len(arr[i])):
            print(i - 100000, arr[i][j])    #y좌표 개수만큼 출력

 

-파이썬( sort 함수 재정의 )

import sys
readline = sys.stdin.readline
n = int( readline() )

arr = [ [0]*2 for _ in range( n ) ]

for i in range( n ):
    a, b = map( int, readline().split() )
    arr[i][0] = a; arr[i][1] = b

arr.sort( key= lambda x : ( x[0], x[1] ) )

for i in range( n ):
    print( arr[i][0], arr[i][1] )