[Greedy] 씨름 선수

 

내 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Player> players = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int height = Integer.parseInt(input[0]);
            int weight = Integer.parseInt(input[1]);

            players.add(new Player(height, weight));
        }

        // players 정렬
        Collections.sort(players, (p1, p2) -> {
            if (p1.height - p2.height != 0) return p2.height - p1.height;
            else return p2.weight - p1.weight;
        });

        int answer = 1;

        int max = players.get(0).weight;

        for (int i = 1; i < players.size(); i++) {
            Player p = players.get(i);
            if (max < p.weight) {
                answer++;
                max = p.weight;
            }
        }

        System.out.println(answer); ;
    }

    static class Player {
        int height;
        int weight;

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

 

 

 

compare 정렬 방식 : 결과값이 양수일 때 자리를 바꾼다.

객체 정렬 (NlogN)

Collections.sort(정렬할 컬렉션 자료구조, () -> {});

() -> {} 
() : 비교할 두 객체, 타입을 쓰지 않는다. (p1, p2)
{} : 비교 조건 {return p2.height - p1.height}

- compare 정렬 방식 : 결과값이 양수일 때 자리를 바꾼다.



p2.height - p1.height > 0 이라면 p1, p2의 자리를 변경한다 : 내림차순
p1.height - p2.height > 0 이라면 p1, p2의 자리를 변경한다 : 오름차순


(a, b) -> {return a - b} : 오름차순 정렬
(a, b) -> {return b - a} : 내림차순 정렬

 

 

Greedy

- '나보다도 키도 크고 몸무게도 무거운 사람이 있으면 탈락'

=> 나보다 키 큰 사람들을 모두 모았을 때 '그 중 나보다 몸무게가 무거운 사람이 한 명도 없다면 나는 합격'

 

- 컬렉션 정렬 - Collections.sort( ... )

- 역순 정렬 : Collections.sort(list, Collections.reverseOrder());

-

 

- 배열 정렬 - Arrays.sort( ... ) 

 

 

• "전부 비교하긴 너무 많네? ($O(N^2)$ 불가)"
• "키 순서대로 줄을 세워볼까? (정렬)"
• "어? 키 순서대로 서니까 나보다 키 큰 사람들은 이미 다 내 앞에 있네? 그럼 몸무게만 비교하면 되네!"
• "그럼 '나보다 키 큰 사람들 중 가장 무거운 몸무게'보다만 내가 더 무거우면 되겠네! (최댓값 경신)" => 그리디

 

 

 

implements Comparable <> 방식

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Player> players = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int height = Integer.parseInt(input[0]);
            int weight = Integer.parseInt(input[1]);

            players.add(new Player(height, weight));
        }

        // players 정렬
        Collections.sort(players);

        int answer = 1;

        int max = players.get(0).weight;

        for (int i = 1; i < players.size(); i++) {
            Player p = players.get(i);
            if (max < p.weight) {
                answer++;
                max = p.weight;
            }
        }

        System.out.println(answer); ;
    }

    static class Player implements Comparable<Player> {

        public int height;
        public int weight;

        public Player(int h, int w) {
            this.height = h;
            this.weight = w;
        }

        @Override
        public int compareTo(Player o) {
            // o(상대방)의 키가 더 크면 양수를 반환해서 자리를 바꿈 -> 내림차순
            return o.height - this.height;
        }
    }
}

 

 

 

구분	Comparable	Comparator
의미	"나는 정렬 가능한 객체다" (자기 자신)	"나는 정렬을 해주는 도구다" (제3자)
구현 메서드	compareTo(T o)	compare(T o1, T o2)
패키지	java.lang (기본 제공)	java.util (유틸 도구)
비유	학생이 스스로 자기 번호표를 들고 있는 것	선생님이 학생 둘을 불러다 키를 재는 것