씨름 선수

좌표정렬 - implement Comparable, 구현하는 compareTo(obejct o) 메서드는 

this - o 하면 오름차순, o - this 하면 내림차순, 만든 후 Collections.sort로 정렬하자

 

그리디 - 한 요소를 정렬 후 정렬되지 않은 요소에서 최선의 결과를 선택하는 방법?으로 이해했다

 

A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가

존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.

N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.

 

입력

5
172 67
183 65
180 70
170 72
181 60

 

출력 3

 

2중 for문 쓰면 n이 최대 3만개라 시간초과가 난다..

요소 2개가 잇을때 하나를 정렬하고 

다음 요소만 비교해서 O(n)의 시간복잡도를 가지게 정렬해야 한다

문제에서는 키와 몸무게 중 키는 먼저 정렬하고 키가 제일 큰 사람의 몸무게를 max로 잡은후 

max 보다 작은 몸무게를 가진 사람은 탈락, max보다 큰 몸무게를 가지면 max를 그 사람의 몸무게로 갱신하는 for문을 돌았다

 

import java.util.*;
class point implements Comparable<point>{
    int height;
    int weight;
    point(int height, int weight) {
        this.height = height;
        this.weight = weight;
    }

    @Override
    public int compareTo(point o) {
        return o.height - this.height;
    }
}

class Main{
    static ArrayList<point> arr;
    static int res = 1, max = Integer.MIN_VALUE;

    public void Solution(ArrayList<point> arr){
        max = arr.get(0).weight;
        for (int i =1; i < arr.size(); i++){
            if (arr.get(i).weight > max) {
                res++;
                max = arr.get(i).weight;
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        arr = new ArrayList<>();
        for (int i = 0; i < n; i++) arr.add(new point(in.nextInt(), in.nextInt()));
        Collections.sort(arr);
        T.Solution(arr);
        System.out.println(res);
    }
}