씨름선수

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		ArrayList<Person> list = new ArrayList<Main.Person>();
		int size = sc.nextInt();
		for (int i = 0; i < size; i++) {
			list.add( T.new Person( sc.nextInt(), sc.nextInt() ) );
		}
		Collections.sort(list,Comparator.reverseOrder());
		
		System.out.println(T.solution(list));
		
		sc.close();
	}
	
	private int solution(ArrayList<Person> list) {
		int max = Integer.MIN_VALUE;
		int cnt = 0;
		
		for (Person person : list) {
			if(max<person.weight) {
				cnt++;
				max = person.weight;
			}
		}
		return cnt;
	}

	class Person implements Comparable<Person>{
		int height;
		int weight;
		public Person(int height, int weight) {
			super();
			this.height = height;
			this.weight = weight;
		}
		@Override
		public int compareTo(Person o) {
			return Integer.compare(this.height, o.height);
		}
		@Override
		public String toString() {
			return height+" "+weight;
		}
	}
	
}

---

입력

5
172 67
183 65
180 70
170 72
181 60

---

결과

3

---

넓은 의미의 그리디 알고리즘, 당장 최선의 선택을 함

키로 정렬해두면, 몸무게만 고려하면 됨