문제 이해
- 특정 선수에 비해 키와 몸무게가 둘 다 높은 선수가 존재하면 해당 선수는 탈락시킨다.
해결 전략
- 키를 기준으로 내림차순 정렬합니다.
- 몸무게의 최대값을 max로 설정하고, 몸무게가 max로 업데이트될 때마다 한 명씩 추가합니다.
-> 몸무게가 최대값으로 업데이트된다는 것은 해당 선수가 키는 더 작더라도, 몸무게는 더 많이 나간다는 것을
의미하기 때문입니다.
구현
import java.util.*;
class Body implements Comparable<Body>{
int h;
int w;
public Body(int h, int w){
this.h = h;
this.w = w;
}
@Override
public int compareTo(Body obj){
return obj.h-this.h;
}
}
public class Main {
public int solution(ArrayList<Body> arr, int n){
Collections.sort(arr);
int max = Integer.MIN_VALUE;
int cnt = 0;
for(Body obj: arr){
if(obj.w > max){
max = obj.w;
cnt++;
}
}
return cnt;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
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));
}
System.out.println(T.solution(arr, n));
}
}
피드백
- 하나를 기준으로 정렬한 후, 최대값을 업데이트해나가는 방식으로 답을 구한다.
'PS' 카테고리의 다른 글
| Leetcode 83. Remove Duplicates from Sorted List (0) | 2022.04.24 |
|---|---|
| 자바(Java) 알고리즘 문제 풀이 - 결혼식 (1) | 2022.04.24 |
| 자바(Java) 알고리즘 문제 풀이 - 회의실 배정 (2) | 2022.04.20 |
| 자바(Java) 알고리즘 문제 풀이 - 섬나라 아일랜드(DFS) (0) | 2022.04.13 |
| 자바(Java) 알고리즘 문제 풀이 - 토마토(BFS 활용) (0) | 2022.04.13 |