[JAVA] 11650번 좌표 정렬하기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

정렬문제이다.

x좌표와 y좌표를 정렬해야하니까 2차원 배열을 만들어서 접근을 해야한다.

 

 

시간복잡도

정렬의 시간복잡도는 O(NlogN)이고 점의 개수 N은 최대 1000,000개니까 

O(NlogN)은 500,000번의 연산으로 계산된다

 

두번째 x좌표가 같으면 y좌표가 증가하는 순서로 정렬이다, 둘다 오름차순으로 정렬을 하면 된다

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. n을 입력받는다

2. n번 만큼 for문을 돌면서 입력값을 받으면서 동시에 배열에 채운다

=> BufferedReader는 문자열로 입력을 받기 때문에, String형 이중배열을 선언하고,

integer로 변환하여 넣어준다.

3. 2차원 배열 정렬을 한다

=> Arrays.sort() 자체는 2차원 배열의 정렬을 할 수가 없다.  그렇기 때문에 람다식을 이용해야함

 

람다식 X
int c = sum(a, b);
public int sum(int a, int b) {
return a + b;
}

람다식 O
int c = (int a, int b) -> {return a + b};

이렇게 쓸 수 있다.

람다식으로 배열의 첫번째 요소를 비교해서 같으면, 두번째 요소를 비교해서 정렬( n1[1] - n2[1])

하고 아니면 첫번째 요소를 기준으로 오름차순한다

비교함수는

 

• 음수: 첫 번째 요소가 두 번째 요소보다 작음
• 0: 두 요소가 같음
• 양수: 첫 번째 요소가 두 번째 요소보다 큼

그래서 비교를 하게 되면

 

• 만약 n1[1] < n2[1]이면, n1[1] - n2[1]은 음수입니다. 따라서 n1이 n2보다 앞에 오게 됩니다.
• 만약 n1[1] > n2[1]이면, n1[1] - n2[1]은 양수입니다. 따라서 n1이 n2보다 뒤에 오게 됩니다.
• 만약 n1[1] == n2[1]이면, n1[1] - n2[1]은 0입니다. 두 요소의 순서는 바뀌지 않습니다.

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int n = Integer.parseInt(br.readLine());
		
		int arr[][] = new int[n][2];
		
		for(int i=0; i<n; i++) {
			String[] str = br.readLine().split(" ");
			arr[i][0] = Integer.parseInt(str[0]);
			arr[i][1] = Integer.parseInt(str[1]);
		}
		
		Arrays.sort(arr, (n1, n2) -> n1[0]==n2[0] ? n1[1]-n2[1] : n1[0]-n2[0]);
		
		
		for (int i=0; i<arr.length; i++) {
			System.out.println(arr[i][0]+ " "+arr[i][1]);
		}
	}
}