씨름 선수

설명

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다.

현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.

현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.

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

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

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

 

입력

첫째 줄에 지원자의 수 N(5<=N<=30,000)이 주어집니다.

두 번째 줄부터 N명의 흰돌 능력치와 검은돌 능력치 정보가 차례로 주어집니다.

각 선수의 흰돌능력치가 모두 다르고, 검은돌 능력치도 모두 다릅니다. 능력치 값은 1,000,000이하의 자연수입니다.

 

출력

첫째 줄에 바둑 선수로 뽑히는 최대 인원을 출력하세요.

 

예시 입력 1 

5
172 67
183 65
180 70
170 72
181 60

 

예시 출력 1

3

힌트

출력설명

(183, 65), (180, 70), (170, 72) 가 선발됩니다. (181, 60)은 (183, 65)보다 키와 몸무게 모두 낮기 때문에 탈락이고, (172, 67)은 (180, 70) 때문에 탈락입니다.

 

문제 해결

 

이 문제는 A라는 지원자를 다른 모든 지원자와 비교했을 때, 키와 몸무게 모두 A보다 높은 지원자가 있다면 A는 탈락하고, 그렇지 않으면 A는 선발되는 문제이다.

 

class Applicant {
    int height;
    int weight;

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

• 우선 각 지원자의 키와 몸무게 정보가 담긴 Applicant 클래스 생성한다.

 

Scanner in = new Scanner(System.in);
int n = in.nextInt();

List<Applicant> applicants = new ArrayList<>();

for (int i = 0; i < n; i++) {
    int height = in.nextInt();
    int weight = in.nextInt();
    applicants.add(new Applicant(height, weight));
}

• 각 지원자의 키와 몸무게 정보를 Applicant 객체로 만들어 리스트에 저장한다.

정렬 전

Collections.sort(applicants, (a1, a2) -> a2.height - a1.height);

• 키가 큰 지원자부터 비교하면, 이후에는 몸무게만 비교하면 되므로 지원자들을 키를 기준으로 내림차순 정렬한다.

TreeSet<Integer> weights = new TreeSet<>(Collections.reverseOrder());
int applicantCount = 0;

for (Applicant applicant : applicants) {
    if (weights.isEmpty() || applicant.weight > weights.first()) {
        applicantCount++;
        weights.add(applicant.weight);
    }
}

• TreeSet을 내림차순으로 정렬해 현재까지 선발된 지원자의 몸무게를 저장하고 각 지원자를 순회하면서 TreeSet에서 가장 큰 몸무게보다 현재 지원자의 몸무게가 크면 선발한다. (
  • (TreeSet은 정렬된 순서를 유지하는 데이터 구조이므로 이와 같은 상황에 사용하기 좋음!! )
  • weights.first()를 통해 현재까지의 최대 몸무게를 얻을 수 있음.

• weights가 비어있거나, 현재 지원자의 몸무게가 weights에서 가장 큰 값보다 크다면 선발
• 선발된 지원자의 수를 증가시키고, weights에 현재 지원자의 몸무게를 추가

 

 

최종 코드

 

import java.util.*;

public class P01_씨름선수 {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        List<Applicant> applicants = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int height = in.nextInt();
            int weight = in.nextInt();
            applicants.add(new Applicant(height, weight));
        }

        Collections.sort(applicants, (a1, a2) -> a2.height - a1.height);

        TreeSet<Integer> weights = new TreeSet<>(Collections.reverseOrder());
        int applicantCount = 0;

        for (Applicant applicant : applicants) {
            if (weights.isEmpty() || applicant.weight > weights.first()) {
                applicantCount++;
                weights.add(applicant.weight);
            }
        }
        
        System.out.println(applicantCount);
    }
}

class Applicant {
    int height;
    int weight;

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