장난꾸러기 / 좌표 정렬

좌표 정렬

✏️ 문제

* 설명
N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.
정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.

* 입력
첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.
두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.

* 출력
N개의 좌표를 정렬하여 출력하세요.

🔍풀이 1

Comparator 를 상속

1. Comparator를 상속한 뒤, compare을 Override해준다.
2. 정렬하고싶은 List이름.sort(new ClassName()); 생성자로 메소드호출.

Compare()의 작동 원리
양수 반환 => 바꾼다.
음수 반환 => 바꾸지 않는다.

class Point implement Comparator<Point> {
	int x, y;
    public Point(int x, int y){this.x = x; this.y = y}
    public Point(){}; // Comparator.sort() 호출을 위한 기본생성자 생성 필수
    @Override
    public int compare(Point o1, Point 02){
    // 뒤에 있는 항이 더 크면 음수 =>바꾸지 않는다 => 오름차순
    	if(o1.x == o2.x) return o1.y-o2.y;  // x값이 같은경우 y로 정렬
        else return o1.x - o2.x;        
    }
}

public class Main {
	public static void main(String[] args){
    	Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Point> arr = new ArrayList<>();
        for(int i = 0; i< n; i++){
        	int x = sc.nextInt();
            int y = sc.nextInt();
            arr.add(new Point(x, y));
        }
        arr.sort(new Point()); //정렬 완료
    }
}

🔍풀이 2

Comparable 상속

class Point implement Comparable<Point> {
	int x, y;
    public Point(int x, int y){this.x = x; this.y = y}
    // 정렬을 위한 기본생성자 필요하지 않음
    @Override
    public int compareTo(Point o){ // o1 -> this o2 -> o로 변경
    	if(this.x == o.x) return this.y-o.y;
        else return this.x - o.x;        
    }
}

public class Main {
	public static void main(String[] args){
    	Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Point> arr = new ArrayList<>();
        for(int i = 0; i< n; i++){
        	int x = sc.nextInt();
            int y = sc.nextInt();
            arr.add(new Point(x, y));
        }
        Collections.sort(arr); 
        //sort는 Point에 재정의한 CompareTo로 적용된다.
    }
}

장난꾸러기

✏️ 문제

* 설명
새 학기가 시작되었습니다. 철수는 새 짝꿍을 만나 너무 신이 났습니다.
철수네 반에는 N명의 학생들이 있습니다.
선생님은 반 학생들에게 반 번호를 정해 주기 위해 운동장에 반 학생들을 키가 가장 작은 학생부터 일렬로 키순으로 세웠습니다.
제일 앞에 가장 작은 학생부터 반 번호를 1번부터 N번까지 부여합니다. 철수는 짝꿍보다 키가 큽니다.
그런데 철수가 앞 번호를 받고 싶어 짝꿍과 자리를 바꿨습니다.
선생님은 이 사실을 모르고 학생들에게 서있는 순서대로 번호를 부여했습니다.
철수와 짝꿍이 자리를 바꾼 반 학생들의 일렬로 서있는 키 정보가 주어질 때 철수가 받은 번호와 철수 짝꿍이 받은 번호를
차례로 출력하는 프로그램을 작성하세요.

* 입력
첫 번째 줄에 자연수 N(5<=N<=100)이 주어진다.
두 번째 줄에 제일 앞에부터 일렬로 서있는 학생들의 키가 주어진다.
키(높이) 값 H는 (120<=H<=180)의 자연수 입니다.

* 출력
첫 번째 줄에 철수의 반 번호와 짝꿍의 반 번호를 차례로 출력합니다.

🔍풀이

정렬 이후 비교하여 다른 부분을 찾는다.

public ArrayList<Integer> solution(int n, int[] arr) {
    ArrayList answer = new ArrayList();
    int[] arr2 = arr.clone();
    Arrays.sort(arr2);
    for(int i = 0; i < arr.length; i++){
        if(arr[i] != arr2[i]) answer.add(i+1);
    }

    return answer;
}