[백준 온라인저지]덩치 - 브루트포스(3)

덩치

이번 포스팅 문제는 7568번 문제입니다. 이 문제 역시 브루트포스를 이용하여 풀이하였습니다.

문제요약

사람의 덩치를 비교할 때 키와 몸무게를 이용합니다. 사람1의 키와 몸무게가 사람2의 키와 몸무게보다 모두 더 클 때 사람1의 덩치가 사람2보다 크다고 말합니다. 덩치 순위는 자신보다 덩치가 큰 사람의 수+1 이며 키와 몸무게가 같더라도 같은 덩치순위를 가질 수 있을 때 주어진 사람들의 덩치 순위를 출력하는 문제입니다. 

풀이전략

1. 키와 몸무게를 데이터로 표현(저는 Person 클래스를 작성하여 이용)

2. 키와 몸무게를 비교하는 알고리즘 구현

3. 이중 반복문을 이용하여 자신보다 덩치가 큰 사람이 있을 때 덩치순위를 1증가

구현하기

package BackJoon.브루트포스;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/7568
 * @author troh
 *
 */
public class _7568_덩치 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int personNumber = sc.nextInt();
        Person[] persons = new Person[personNumber];
        for(int i=0; i<personNumber; i++) {
            int weight = sc.nextInt();
            int height = sc.nextInt();
            
            Person p = new Person(weight, height);
            persons[i] = p;
        }
        
        int[] ranks = getRanks(persons);
        for(int i=0; i<ranks.length; i++) {
            System.out.printf("%d ", ranks[i]);
        }
    }
    
    private static int[] getRanks(Person[] persons) {
        int[] ranks = new int[persons.length];
        
        // 모든 사람들을 순회하며 자신보다 덩치가 크면 rank를 증가시켜서 저장시킴
        for(int i=0; i<persons.length; i++) {
            int p1Rank = 1;
            Person p1 = persons[i];
            
            for(int j=0; j<persons.length; j++) {
                if(i==j) continue;
                
                Person p2 = persons[j];
                if(p2.compareTo(p1) == 1) {
                    p1Rank ++;
                }
            }
            ranks[i] = p1Rank;
        }
        return ranks;
    }
}
 
class Person implements Comparable<Person>{
    private int weight;
    private int height;
    
    public Person(int weight, int height) {
        this.weight = weight;
        this.height = height;
    }
 
    // Comparable 인터페이스를 구현하여 덩치비교
    @Override
    public int compareTo(Person o) {
        if(this.weight > o.weight && this.height > o.height ) {
            return 1; 
        } else if((this.weight == o.weight || this.weight > o.weight) && (this.height == o.height || this.height < o.height)) {
            return 0;
        } else if((this.weight == o.weight || this.weight < o.weight) && (this.height == o.height || this.height > o.height)) {
            return 0;
        } else {
            return -1;
        }
    }
}
 

배운점

다차원 배열을 이용했어도 문제를 해결했을 수 있을 것 같습니다. 그랬으면 메모리 사용량이 줄지 않을까 생각됩니다..