[JAVA/코딩테스트] 씨름 선수(Greedy Algorithm)

Recent Posts

Recent Comments

관리 메뉴

🌷🌼모여봐요 개발의숲🌷🌼

[JAVA/코딩테스트] 씨름 선수(Greedy Algorithm) 본문

개발/알고리즘 문제풀이 JAVA

[JAVA/코딩테스트] 씨름 선수(Greedy Algorithm)

요일이 2022. 2. 12. 00:09

설명

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

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

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

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

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

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

입력

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

두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다.

값은 1,000,000이하의 자연수입니다.

출력

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

예시 입력 1

예시 출력 1

힌트

출력설명

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

import java.util.*;

class Body implements Comparable<Body>{

    public int height;
    public int weight;

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

    @Override
    public int compareTo(Body o){
        if(this.height==o.height) {
            return o.weight - this.weight;
        }else{
            return o.height - this.height;
        }
    }

}


public class Main {

    static int[][] array;

    public int solution(int n, ArrayList<Body> body) {

        int result = 0;
        int max = 0;

        for(int i=0; i<n; i++){
            if(max<body.get(i).weight){
                max = body.get(i).weight;
                result++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();

        ArrayList<Body> body = new ArrayList<>();

        for(int i=0; i<n; i++){
            Body tmp = new Body(kb.nextInt(), kb.nextInt());
            body.add(tmp);
        }

        Collections.sort(body);

        System.out.println(main.solution(n, body));
    }

}

저작자표시 비영리 변경금지

'개발 > 알고리즘 문제풀이 JAVA' 카테고리의 다른 글

[JAVA/코딩테스트] 최대 수입 스케쥴(PriorityQueue 응용문제) (0)	2022.02.15
[JAVA/코딩테스트] 결혼식 (0)	2022.02.14
[JAVA/코딩테스트] 조합의 경우수(메모이제이션) (0)	2022.02.10
[JAVA/코딩테스트] 순열구하기 (0)	2022.02.08
[JAVA/코딩테스트] 동전교환 (0)	2022.01.30

'개발/알고리즘 문제풀이 JAVA' Related Articles

Comments

🌷🌼모여봐요 개발의숲🌷🌼

[JAVA/코딩테스트] 씨름 선수(Greedy Algorithm) 본문

[JAVA/코딩테스트] 씨름 선수(Greedy Algorithm)

'개발 > 알고리즘 문제풀이 JAVA' 카테고리의 다른 글

티스토리툴바