인프런, 자바(Java) 알고리즘 문제풀이
Greedy Alogorithm - 0901. 씨름 선수
🗒️ 문제
🎈 나의 풀이
public static class Man implements Comparable<Man> {
int h, w;
public Man(int h, int w) {
this.h = h;
this.w = w;
}
@Override
public int compareTo(Man o) {
if(h == o.h) return w - o.w;
else return h - o.h;
}
}
private static int solution(List<Man> list) {
Collections.sort(list, Collections.reverseOrder());
int answer = list.size();
int heavy = 0;
for(Man m : list) {
if(heavy == 0) heavy = m.w;
else {
if(m.w < heavy) answer--;
heavy = Math.max(heavy, m.w);
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<Man> list = new ArrayList<>();
int n = sc.nextInt();
for(int i=0; i<n; i++) {
int h = sc.nextInt();
int w = sc.nextInt();
list.add(new Man(h, w));
}
System.out.println(solution(list));
}🖍️ 강의 풀이
class Body implements Comparable<Body>{
public int h, w;
Body(int h, int w) {
this.h = h;
this.w = w;
}
@Override
public int compareTo(Body o){
return o.h-this.h;
}
}
class Main {
public int solution(ArrayList<Body> arr, int n){
int cnt=0;
Collections.sort(arr);
int max=Integer.MIN_VALUE;
for(Body ob : arr){
if(ob.w>max){
max=ob.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));
}
}💬 짚어가기
해당 문제는 Greedy Algorithm를 이용하여 풀 수 있다.
Greed Alogrithm
선택의 순간마다 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 그리디 알고리즘
적용을 위해선 아래 2가지 조건을 충족해야한다.
탐욕적 선택 속성(Greedy Choice Property)
: 앞의 선택이 이후의 선택에 영향을 주지 않는다.최적 부분 구조(Optimal Substructure)
: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
나의 풀이에서는 선수의 키와 몸무게 정보를 담을 수 있는 클래스를 생성하고, 정렬을 위해
Comparable 인터페이스의 compareTo() 메소드를 재정의 하였다.
다음 키 순으로 정렬된 선수 리스트를 순회하며 몸무게 조건을 확인하여 문제를 해결하였다.
𝑶𝒏𝒆 𝒅𝒂𝒚 𝒐𝒓 𝒅𝒂𝒚 𝒐𝒏𝒆.