씨름 선수(Greedy)

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

 

현수는 씨름 선수 선발을 위해 공고를 냈으며, 총 N명의 지원자가 지원하였다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있으며, 선발 원칙은 다음과 같다.

"한 지원자를 다른 모든 지원자와 비교하여, 키와 몸무게 모두 더 큰 지원자가 존재하면 해당 지원자는 탈락하고, 그렇지 않으면 선발된다."

 

즉, 키와 몸무게 모두 더 큰 지원자가 존재하면 해당 지원자는 탈락하고, 그렇지 않으면 선발된다. N명의 지원자가 주어지면 이 원칙에 따라 최대 몇 명의 선수를 선발할 수 있는지를 알아내는 프로그램을 작성하시오.

 

입력 설명

• 첫째 줄에 지원자의 수 N이 주어진다. (5 ≤ N ≤ 100,000)
• 두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어진다. 각 지원자의 키와 몸무게는 모두 다르다.

출력 설명

• 첫째 줄에 씨름 선수로 선발될 수 있는 최대 인원을 출력한다.

입력예제 

5
172 67
183 65
180 70
170 72
181 60

 

출력예제 

3

 

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

 

문제 해결 과정

1. 정렬 기준 설정
   먼저 지원자들의 리스트를 키를 기준으로 내림차순으로 정렬한다. 이는 큰 키부터 비교할 수 있도록 하여, 앞에 있는 지원자가 이미 뒤에 있는 사람보다 키가 크므로, 몸무게만 비교하면 되는 상황을 만든다.
2. 몸무게 비교
   키를 내림차순으로 정렬한 후, 몸무게만 비교하여 더 큰 몸무게를 가진 지원자를 카운트한다.
   즉, 리스트를 순회하면서 현재까지 확인한 몸무게 중 가장 큰 값을 유지하고, 이를 넘는 지원자만 선발한다.

알고리즘 설명

1. 정렬: 키를 기준으로 내림차순 정렬한다. 이로써, 큰 키의 지원자부터 탐색이 이루어지며, 이후로는 몸무게만 비교하면 된다.
2. 몸무게 비교: 리스트를 순회하면서 현재까지 확인된 가장 큰 몸무게(max)보다 큰 경우에만 해당 지원자를 선발한다. 이를 통해 키와 몸무게 모두 더 큰 지원자가 없는지를 확인할 수 있다.

코드

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Person {
    int h, w;
    public Person(int h, int w) {
        this.h = h;
        this.w = w;
    }
}

class Main {
    public static int solution(ArrayList<Person> arr) {
        // 키를 기준으로 내림차순 정렬
        arr.sort((a, b) -> b.h - a.h);
        int cnt = 0, max = Integer.MIN_VALUE;

        // 몸무게를 비교하여 선발 가능한 지원자를 카운트
        for (Person ob : arr) {
            if (ob.w > max) {  // 현재 지원자의 몸무게가 max보다 크면 선발
                max = ob.w;
                cnt++;
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());  // 지원자 수 입력
        ArrayList<Person> person = new ArrayList<>();

        // 지원자의 키와 몸무게 입력
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            person.add(new Person(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // 선발된 최대 인원 출력
        System.out.println(solution(person));
    }
}

설명

• 입력 처리: 각 지원자의 키와 몸무게를 입력받아 Person 객체로 리스트에 저장한다.
• 정렬: arr.sort((a, b) -> b.h - a.h);를 통해 키를 기준으로 내림차순 정렬한다.
• 몸무게 비교: 정렬된 리스트를 순회하면서 현재까지 확인된 가장 큰 몸무게(max)보다 큰 지원자만 선발하여 카운트한다.
• 출력: 최종적으로 선발된 최대 인원을 출력한다.

핵심 아이디어

1. 키를 내림차순으로 정렬하면, 앞의 지원자는 뒤에 있는 지원자보다 항상 키가 크다. 그러므로 몸무게만 비교하면 된다.
2. 몸무게 비교에서 가장 큰 값만 계속 유지하면서 그보다 큰 지원자만 선발하는 방식으로 간단히 해결할 수 있다.

시간 복잡도

• 정렬에 걸리는 시간은 O(N log N)이며, 리스트를 순회하는 데 걸리는 시간은 O(N)이다. 따라서 전체 시간 복잡도는 O(N log N)이다.

결론

이 알고리즘은 키와 몸무게라는 두 가지 조건을 효율적으로 처리하기 위해 정렬 후 비교 방식을 사용하여 문제를 해결한다.