[Algorithm] 백준_덩치_7568번 (JAVA)

📝문제

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

덩치 7568

티어: Silver 5

💡풀이

문제 유형

완전탐색

 

걸린 시간

20분

 

시간 복잡도

O(N^2)

 

풀이 방법 도출

1. N의 최대 크기가 50이므로 완전탐색을 해도 시간초과 우려가 없다.
2. 몸무게 배열 weight와 키 배열 height를 만들어주고
3. 반복문을 돌려 현재 몸무게와 키를 구하고 이에 대해 한 번 더 반복문을 돌린다.
4. 현재 몸무게와 키보다 큰 경우에만 카운트를 하고
5. rank 배열에 현재의 등수를 넣어준다.

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] weight = new int[N];
        int[] height = new int[N];
        int[] rank = new int[N];

        StringTokenizer st;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            weight[i] = x;
            height[i] = y;
        }

        for(int i = 0; i < N; i++){
            int x = weight[i];
            int y = height[i];
            int k = 0;
            for(int j = 0; j < N; j++){
                if(i == j) continue;
                if(weight[j] > x && height[j] > y){
                    k++;
                }
            }
            rank[i] = k+1; //덩치 등수
        }

        StringBuilder sb = new StringBuilder();
        for(int n : rank){
            sb.append(n).append(" ");
        }

        System.out.println(sb);
    }
}

 

🤔Review

부르트포스, 완전탐색, 1초에 1억번 실행...