[JAVA] 백준 7568_덩치

[문제링크]

https://www.acmicpc.net/problem/7568

 

 

📌 가능한 시간복잡도

이중 반복문을 사용하니까 시간 복잡도는N , N 두번

따라서, 가능한 시간복잡도는 O(N^2)이다. 

 

📌 코드 설계하기

먼저 몸무게랑 키를 입력받고 이중 반복문을 활용해서 i번째를 기준으로 j들과 비교해서 자신보다 몸무게랑 키가 둘 다 큰 사람을 발견하면 rank++ 으로 등수를 올리는 방식을 반복해서 등수를 순서대로 출력하면 된다. 

 

📌 정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        int[] weights = new int[N];
        int[] heights = new int[N];

        for (int i = 0; i < N; i++) {
            weights[i] = in.nextInt(); 
            heights[i] = in.nextInt(); 
        }

        int[] ranks = new int[N];

        for (int i = 0; i < N; i++) {
            int rank = 1; // 기본 등수 1
            for (int j = 0; j < N; j++) {
                if (i != j) { 
                    if (weights[j] > weights[i] && heights[j] > heights[i]) {
                        rank++;
                    }
                }
            }
            ranks[i] = rank; 
        }

        for (int i = 0; i < N; i++) {
            System.out.print(ranks[i] + " ");
        }
    }
}