설명
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, 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) 때문에 탈락입니다.
이 문제 풀기 전 Chapter06 좌표정렬 학습 후 도전 [O]
문제 이해
O(N)으로 가능
수도 코드 및 정답 코드
import java.util.*;
class Body implements Comparable<Body> {
int h,w;
// 매개변수 있는 생성자
Body(int h, int w){
this.h=h;
this.w=w;
}
// 오버라이드, compareTo메서드로 정렬
@Override
public int compareTo(Body b) {
// 키로 내림차순 b-this 음수
return b.h - this.h;
}
}
public class Wrestling {
public int solution(ArrayList<Body> arr) { // 타입 주의!
// return
int cnt =0;
// 임시 변수 max 설정 - 최솟값, 앞에서부터 몸무게 비교
int max = Integer.MIN_VALUE;
// 몸무게만 비교니까 몸무게만 빼올 수 없을까 : ob.w로 접근 가능!!!
for(Body ob : arr) {
if(ob.w > max) {
// max 탈환하고 cnt++
max = ob.w;
cnt++;
}
}
return cnt;
}
public static void main(String[] args) {
Wrestling T = new Wrestling();
Scanner kb = new Scanner(System.in);
// 입력 두번 : 총 n번, ArrayList로 n번
int n = kb.nextInt();
// ArrayList 선언
ArrayList<Body> arr = new ArrayList<>();
for(int i=0; i<n; i++) {
int h = kb.nextInt();
int w = kb.nextInt();
arr.add(new Body(h,w)); // 객체 생성해서 넣음!
}
Collections.sort(arr); // Body클래스에 의해서 키로 정렬되어짐
System.out.println(T.solution(arr));
}
}
💡 [주의] 넘길 때 타입 명시
public int solution(ArrayList<Body> arr) { }
💡 일시적 max, min 설정
최솟값 : int min = Integer.MIN_VALUE;
최댓값 : int max = Integer.MAX_VALUE;
💡 ArrayList로 객체 담을 때, 한 요소만 가져오는 방법
for(Body ob : arr) { if(ob.w > max) { ... } }