문제 풀이(41)

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

import java.util.*;
import java.io.*;

class Main{

    static int N;
    static int[][] matrix;
    static boolean[] visited;
    static int[] selected;
    static HashMap<Integer,Integer>map = new HashMap<>();

    public static void main(String[] args) throws IOException {
    
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            map.put(i, 1);
        }

        selected = new int[2];

        visited = new boolean[N];

        matrix = new int[N][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int w = Integer.parseInt(st.nextToken());

            int h = Integer.parseInt(st.nextToken());

            matrix[i][0] = w;

            matrix[i][1] = h;

            
        }

        rec_func(0 , 0);

        for (int i = 0; i < N; i++) {
            System.out.print(map.get(i)+" ");
        }
    }

    public static boolean function()
    {
        int[] A = matrix[selected[0]];

        int[] B = matrix[selected[1]];

        if (A[0] > B[0] && A[1] > B[1]) {
            map.put(selected[1], map.get(selected[1]) + 1);
        }

        if (A[0] < B[0] && A[1] < B[1]) {
            map.put(selected[0], map.get(selected[0]) + 1);
        }

        return true;
    }

    public static void rec_func(int k, int idx)
    {
        if (k == 2) {
        
            function();

        }else{

            for (int i = idx; i < N; i++) {
                
                selected[k] = i;

                rec_func(k + 1, i + 1);

                selected[k] = 0;
            }

        }
    }

}

N 변수와 matrix 배열:

N 변수는 입력으로 주어지는 사람의 수를 나타낸다.
matrix 배열은 사람들의 몸무게와 키 정보를 저장하는 2차원 배열이다. 각 행은 한 사람의 몸무게와 키를 저장하고 있으며, 각 열은 몸무게(0번 열)와 키(1번 열)를 나타낸다.

visited 배열은 재귀 호출에서 어떤 사람들이 이미 선택되었는지를 나타내는 boolean 배열이다.
selected 배열은 현재 선택된 두 명의 사람을 나타낸다.

map은 각 사람의 덩치 등수를 저장하기 위한 HashMap입니다. 초기에 모든 사람의 덩치 등수를 1로 초기화한다.

function 메서드:

이 메서드는 두 명의 사람(A와 B)을 비교하여 누가 더 큰 덩치인지를 판단하고, 그에 따라 덩치 등수를 업데이트한다.
A가 B보다 몸무게와 키 모두 크다면 B의 덩치 등수를 1 증가시킨다.
A가 B보다 몸무게와 키 모두 작다면 A의 덩치 등수를 1 증가시킨다.

rec_func 메서드:

이 메서드는 재귀 호출을 사용하여 가능한 모든 두 명의 사람 조합을 선택한다.
k는 현재 선택한 사람의 수를 나타낸다. k가 2일 때 (두 명의 사람이 선택되었을 때), function 메서드를 호출하여 두 명의 사람을 비교하고 덩치 등수를 업데이트한다.
재귀적으로 모든 조합을 확인하여 모든 사람의 덩치 등수를 계산한다.