DP-씨름 선수

입력 예시:

5  -->사람 수
172 67 --> 키 몸무게
183 65
180 70
170 72
181 60

import java.util.*;

public class java {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int arr[][] = new int[sc.nextInt()][2];
        for(int i=0;i<arr.length;i++){
            for (int j = 0; j < 2; j++) {
                arr[i][j]=sc.nextInt();
            }
        }

       Arrays.sort(arr, new Comparator<int[]>() {
           @Override
           public int compare(int[] o1, int[] o2) {
               if(o1[0]==o2[0])return o1[1]-o2[1];
               else return o1[0]-o2[0];
           }
       });
        int max=Integer.MIN_VALUE;
        int count=0;
        for(int i=arr.length-1;i>=0;i--){
            if(arr[i][1]>max){
                max=arr[i][1];
                count++;
            }
        }
        System.out.println(count);

    }
}

처음에 이중 배열과 같은 방법을 푸려고 했더니 .. 시간초과 더 생산적인 방법을 했더니 정답은 정렬이였다.

문제에서 원하는 답은 자신보다 키와 몸무게가 높지 않은 사람을 원한느 것.

그렇다면 키를 먼저 정렬한후 자신보다 몸무게가 높지 않은 사람을 찾으면 된다.

 

키	몸무게
170	72
172	67
180	70
181	60
183	65

 Arrays.sort(Array[], Comparator{})을 사용하여 오름차순으로 정렬한 후 해결 했다. 

복잡도는 O(N)으로 풀 수 있었다.