[추가] 씨름선수 - 그리디 문제

🟦 씨름선수 - 그리디 문제

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은 (크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.” N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.

▣ 입력설명 첫째 줄에 지원자의 수 N(5<=N<=100,000)이 주어집니다. 두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두 다릅니다.

▣ 출력설명 첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요

💚나의 풀이 - 그리디

• 이 문제 역시 씨름 선수가 하나라도 뛰어난 게 있어야 선발되는데, 즉 둘 다 뒤쳐지는 선수는 탈락이라는 거다
• 그리디적으로 보면, 키 기준 내림차순 정렬 시켜놓고, 첫 번째 선수는 키가 제일 크니까 (가장 뛰어남) 일단 카운팅.
• 기준값은 첫번째 키 선수의 몸무게로 둔다.
• 이제 이 뒷사람들은 무조건 이 선수보다 키가 작은데, 이 선발된 선수보다 몸무게까지 뒤쳐진다면 continue; 건너뛰고
• 아니라면 카운팅++ 후, 해당 선발 선수의 몸무게로 기준값 갱신

import java.util.ArrayList;
import java.util.Scanner;

/*씨름선수 - 그리디 */
class Person implements Comparable<Person>{
	int k ;
	int mom; 
	Person(int k, int mom){
		this.k = k;
		this.mom = mom;
	}
	@Override
	public int compareTo(Person o) {
		// TODO Auto-generated method stub
		return o.k - this.k ;//키 기준 내림차순 정렬 
	}
}

public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		int n = kb.nextInt();
		ArrayList<Person> arr = new ArrayList<>();
		for(int i=0; i<n; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			arr.add(new Person(a, b));
		}
		
		int answer=  1;
		int pivot = arr.get(0).mom;//기준 값
		
		for(int i=1; i<n; i++) {
			//기준보다 몸 적은 애들은 둘다 뒤쳐지는 애들이므로 탈락
			if(pivot > arr.get(i).mom) continue;
			answer++;
			pivot = arr.get(i).mom;
		}
		
		System.out.println(answer);
	}
}