[인프런 알고리즘] Chapter2, 12번 문제(멘토링)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

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

public class sec02_12 {
    public static int solution(int N, int M, int[][] arr){
        int count = 0;

        // 순위를 저장할 배열
        int[][] rank = new int[M][N + 1];

        // 각 테스트에서 학생들의 순위를 미리 계산
        for (int k = 0; k < M; ++k)
        {
            for (int s = 0; s < N; ++s) rank[k][arr[k][s]] = s;
        }

        // 학생 쌍 (i, j) 에 대해 비교
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j)
            {
                int temp = 0;
                for (int k = 0; k < M; ++k) if (rank[k][i] < rank[k][j]) ++temp;
                if (temp == M) ++count;
            }
        }

        return count;
    }

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

        for(int i = 0; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; ++j) arr[i][j] = Integer.parseInt(st.nextToken());
        }
        System.out.println(solution(N, M, arr));
    }
}

 

설명

• rank 배열은 각 테스트(M)에서 각 학생(N)의 순위를 저장한다.
• rank[k][x]는 k번째 테스트에서 x 학생의 순위를 의미한다.

 

 

for (int k = 0; k < M; ++k) {
    for (int s = 0; s < N; ++s) rank[k][arr[k][s]] = s;
}

• 각 테스트에 대해, 학생들의 순위를 계산하고 rank 배열에 저장한다.
• arr[k][s]는 k번째 테스트에서 s번째 순위인 학생의 번호이다.
• 예를 들어, rank[0][3] = 2라면, 첫 번째 테스트에서 3번 학생은 세 번째 순위라는 뜻이다.

 

for (int i = 1; i <= N; ++i) 
{
    for (int j = 1; j <= N; ++j)
    {
        int temp = 0;
        for (int k = 0; k < M; ++k) if (rank[k][i] < rank[k][j]) ++temp;
        if (temp == M) ++count;
    }
}

• 모든 학생 쌍 (i, j)에 대해 i가 모든 테스트에서 j보다 높은 순위에 있는지를 확인한다.
• 각 테스트마다 rank[k][i] < rank[k][j]인 경우 temp를 증가시킨다.

 

return count;

• 모든 조건을 만족하는 학생 쌍의 수를 반환한다.