[백준] 7568번 : 덩치 자바(JAVA) 풀이

문제

---

---

문제 탐색하기

• N : 전체 사람의 수
• 입력 : 각 사람의 몸무게와 키를 나타내는 정수 x와 y
• 출력 
  1. 덩치가 큰 경우 => 몸무게와 키가 클 때
  2. 자신보다 큰 덩치인 사람이 K명이면 그 사람의 덩치 등수는 K+1
  3. 사람의 덩치 등수를 구해서 순서대로 출력
  4. 등수는 공백문자로 분리

가능한 시간복잡도

입력 범위 ( 2 ≤ N ≤ 50 , 10 ≤ x, y ≤ 200)

1. 입력 받기 : 입력받은 사람의 정보를 배열에 저장할 때 O(N)의 시간 복잡도를 가짐
2. 이중 for문을 사용하여 덩치를 비교해줬으므로 O(N^2)
3. 최종적으로 최악의 경우 시간 복잡도는 O( N^2 ) 

---

코드 설계하기

• N개 사람의 정보를 입력받아 배열에 저장한다.
• 덩치가 크다고 인정되는 경우 : 몸무게와 키 둘 다 클 때
• 자신보다 큰 덩치인 사람 cnt 세고 그 사람의 덩치 등수를 cnt +1로 배열에 담아준다.
• 배열에 저장된 덩치 등수 출력한다.

---

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine()); // 전체 사람 수
        int[][] intArr = new int[num][3]; // 몸무게, 키, 등수 담을 배열
        int cnt = 0; // 등수 count

        // 1. 입력받는 수 배열에 저장
        for(int i=0;i<num;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            intArr[i][0] = Integer.parseInt(st.nextToken()); // 몸무게
            intArr[i][1] = Integer.parseInt(st.nextToken()); // 키
        }

        // 2. 자신과 다른 사람들 for문으로 비교
        for(int i=0;i<num;i++) {
            cnt = 0;
            for (int j = 0; j < num; j++) {
                // 자신보다 큰 덩치가 있으면
                if (intArr[i][0] < intArr[j][0] && intArr[i][1] < intArr[j][1]) {
                    // 자신보다 큰 덩치 사람 수 +1
                    cnt = cnt + 1;
                }
            }
            // 자신 덩치 등수 배열에 저장
            intArr[i][2] = cnt + 1;
        }
        
        // 3. 덩치 등수 출력
        for(int i=0;i<num;i++){
            System.out.print(intArr[i][2] + " ");
        }
    }
}