알고리즘) 씨름 선수(그리디 알고리즘)

그리디 알고리즘

 순간 순간에 가장 최선이라고 여겨지는 선택을 하는 알고리즘을 뜻한다. 전반적인 결과도 최선이라는 보장을 할 수 없다.

문제 ✨

 N명의 지원자의 키와 몸무게 정보를 입력받아 각 지원자가 다른 지원자와 일대일 비교해서 키와 몸무게 모두 높은 지원자가 존재할 경우에는 떨어트리고, 그렇지 않으면 선발한다고 했을 때 N명의 지원자가 주어지면 최대 몇 명의 선수를 선발할 수 있는지 출력한다.

풀이 ✨

 키와 몸무게 정보로 구성된 클래스를 생성한다. 두 가지 속성으로 비교하기 때문에 기본적으로 키를 기준으로 인스턴스들을 역순으로 정렬한 후 순서대로 해당 인스턴스의 몸무게가 여태까지 나온 최대 몸무게보다 클 때에만 탈락하지 않는다고 여긴다.

작성 코드 ✍️

import java.util.*;

public class Main {
    static class Person implements Comparable<Person> {
        int height;
        int weight;

        public Person(int height, int weight) {
            this.height = height;
            this.weight = weight;
        }

        @Override
        public int compareTo(Person o) {
            return o.height - this.height;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Person> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int h = sc.nextInt();
            int w = sc.nextInt();
            list.add(new Person(h, w));
        }

        Collections.sort(list);

        int cnt = 0;
        int max = Integer.MIN_VALUE;
        for (Person p : list) {
            if (p.weight > max) {
                max = Math.max(max, p.weight);
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}