[BOJ] 2016.미팅주선하기

문제

미팅 자리에서 각자의 짝을 정하는 방법은 다음과 같습니다.

1. 태현이가 1번, 나머지 남학생이 2-5번, 여학생이 6-10번입니다.
2. 각자 상대에 대한 선호도 순위를 매겨서 씁니다.
   이때, 두 명 이상의 상대에게 같은 선호도를 적용하면 안 되고, 5명 모두에 대한 순위를 매겨야 합니다.
3. 6번 여학생부터 가장 좋아하는 남학생에게 프러포즈를 하며, 퇴자 맞으면 다음 순서의 남학생에게 프러포즈를 합니다.
4. 남학생은 현재 짝이 없으면 무조건 프러포즈를 받으며,
   두 명 이상인 경우 더 선호하는 여학생과 짝이 되고 나머지 여학생에게 퇴짜를 놓습니다.
5. 퇴짜 받은 여학생들만 다음 라운드에서 짝짓기에 참여합니다.

모든 학생들이 짝을 찾을 때까지 이 과정을 반복하며 마지막에 서로의 짝이 최종 짝이 됩니다.

태현이의 선호도는 6 7 8 9 10 여학생 순서입니다.

해당 선호도를 적당히 바꿔 적어서 원래 선호도 리스트보다 더 좋아하는 여학생과 짝이 될 수 있다면 "YES", 아니면 "NO"를 출력합니다.

풀이

1. 입력을 받을 때 선호도 정보와 인덱스를 기반으로 점수를 기재합니다. ( 0 ~ 4)
2. 태현이의 선호도를 생성합니다. - 수열
3. 위의 방법대로 짝을 정합니다.
   • 이미 짝을 지정한 여학생은 짝 선택을 하지 않습니다.
   • 남학생의 짝이 없는 경우, 현재 프러포즈한 여학생과 짝이 됩니다.
   • 남학생의 짝이 있는 경우, 짝과 현재 여학생의 선호도를 비교하여, 선호도가 더 높은 여학생과 짝이 됩니다. (인덱스 기반 점수 활용)

풀이는 생각보다 더 심플합니다. 실제 코드를 보여드리도록 하겠습니다.

import java.util.Scanner;
 
public class Main {
    static int[] myPreference = {6, 7, 8, 9, 10}; // 태현의 선호도
    static int[] outputPreference = new int[5];
    static int[] outputScores = new int[5];
    static int originPartner = 0;
    static int changePartner = 0;
    static int cnt = 0;
 
    // 짝 정하기
    public static void getPartner(int[][] preference, int[][] scores) {
        preference[1] = outputPreference;
        scores[1] = outputScores;
        int[] partners = new int[11]; // 파트너 정보 기록
        int[] findPartner = new int[5]; // 여학생의 파트너 정보 기록
 
        while (true) {
            boolean isContinue = false;
            for (int i = 6; i < 11; i++) {
                if (partners[i] != 0) continue; // 이미 짝을 지정한 여학생은 짝 선택 X
                int idx = findPartner[i - 6]; // 여학생이 원하는 남학생 우선순위 (인덱스)
                findPartner[i - 6] = idx + 1; // 여학생이 다시 짝을 찾을 때 사용할 인덱스
 
                int wantPartner = preference[i][idx]; // 여학생이 원하는 남학생
                if (partners[wantPartner] == 0) { // 아직 짝이 정해지지 않음
                    partners[wantPartner] = i;
                    partners[i] = wantPartner;
                } else {
                    isContinue = true;
                    int decidedPartner = partners[wantPartner]; // 남학생과 짝인 여학생 번호
                    
                    // 선호도 비교
                    if (scores[wantPartner][decidedPartner - 6] > scores[wantPartner][i - 6]) {
                        partners[wantPartner] = i;
                        partners[i] = wantPartner;
                        partners[decidedPartner] = 0; // 기존에 짝인 여학생은 새로 지정해야 한다.
                    }
                }
            }
            if (!isContinue) break;
        }
 
        if (cnt == 0) {
            originPartner = partners[1];
        } else {
            changePartner = partners[1];
        }
 
    }
 
    // 태현의 선호도 생성
    public static void setPreference(int len, int[][] preference, int[][] scores, boolean[] used) {
        if (1 < cnt && originPartner > changePartner) {
            return;
        }
 
        if (len == 5) {
            // 선호도 결과 구하기
            getPartner(preference, scores);
            cnt++;
            return;
        }
 
        for (int idx = 0; idx < 5; idx++) {
            if (!used[idx]) {
                used[idx] = true;
                int partner = myPreference[idx];
                outputPreference[len] = partner;
                outputScores[partner - 6] = len;
                setPreference(len + 1, preference, scores, used);
                used[idx] = false;
            }
        }
    }
 
    public static String solution(int[][] preferences, int[][] scores) {
        boolean[] used = new boolean[5]; // 선호도 사용 기록
        cnt = 0;
 
        // 선호도 계산
        setPreference(0, preferences, scores, used);
 
        if (originPartner > changePartner) {
            return "YES";
        } else {
            return "NO";
        }
    }
 
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int testcase = input.nextInt();
        int[][] preferences = new int[11][5];
        int[][] scores = new int[11][5]; // 우선순위에 따른 점수
 
        for (int tc = 0; tc < testcase; tc++) {
            // 선호도 입력
            for (int i = 2; i < 11; i++) {
                for (int j = 0; j < 5; j++) {
                    int partner = input.nextInt();
                    preferences[i][j] = partner;
                    if (partner > 5) partner -= 5;
                    scores[i][partner - 1] = j;
                }
            }
            System.out.println(solution(preferences, scores));
        }
 
    }
}