[MVP] Most Valuable Programmer

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/MVP

algospot.com :: MVP

 

풀이입니다. 🤔

 

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int[][] prefers = new int[100][10];
        int[] votes = new int[10], positions = new int[100];
        boolean[] eliminated = new boolean[10];
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt(), m = scanner.nextInt();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    prefers[i][j] = scanner.nextInt() - 1;
                }
            }
 
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int prefer = -1;
                    while (positions[j] < m && prefer == -1) {
                        // 이 부분 구현을 위해 Queue 를 사용해도 좋다.
                        // 이 코드에서는 제거된 프로그래머를 제외하기 위해 prefers 의 Position 만을 제어하고 있다.
                        if (eliminated[prefers[j][positions[j]]]) ++positions[j];
                        else prefer = prefers[j][positions[j]];
                    }
 
                    if (prefer != -1) ++votes[prefer];
                }
 
                int minVote = Integer.MAX_VALUE, minCount = 0, clearedCount = 0;
                for (int j = 0; j < m; ++j) {
                    if (eliminated[j]) ++clearedCount;
                    else {
                        if (minVote == votes[j]) ++minCount;
                        else if (minVote > votes[j]) {
                            minCount = 1;
                            minVote = votes[j];
                        }
                    }
                }
                if (m - clearedCount != minCount) {
                    for (int j = 0; j < m; ++j) if (votes[j] == minVote) eliminated[j] = true;
                }
 
                Arrays.fill(votes, 0);
            }
 
            List<Integer> answers = new ArrayList<>();
            for (int i = 0; i < m; ++i) if (!eliminated[i]) answers.add(i + 1);
            for (int i = 0, size = answers.size(); i < size; ++i) {
                System.out.printf("%d%s", answers.get(i), (i + 1 == size) ? "\n" : " ");
            }
 
            Arrays.fill(eliminated, false);
            Arrays.fill(positions, 0);
        }
    }
}

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️