[백준] 27985 멘토링 매칭

Backjoon

해설

gale-shapley 알고리즘을 기반으로 하고 있으나 쌍이 주어지지 않는다. 중요한 포인트는 다음 부분이다.

 

즉 선호도 테스트 케이스가 다음과 같이 주어지면

5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

 

카이스트 학생들의 선호도는 다음과 같이 나와야 한다. 

5 4 3 2 1
5 4 1 3 2
1 5 2 4 3
1 2 3 5 4
1 2 3 4 5

 

따라서, 저 조건에 맞에 카이스트 학생들의 선호도를 만들어준 후 gale-shapley 알고리즘을 사용하면 풀 수 있다. 필자는 다음과 같이 구현했다.

for i in range(1, n+1):
    temp = [i]
    for dist in range(1,n):
        for j in range(n, 0, -1):
            if abs(i-j) == dist:
                temp.append(j)
    kaist_pref.append(temp[::-1])

 

코드

import sys
input = sys.stdin.readline

n = int(input())
person_pref = [list(map(int, input().split())) for _ in range(n)]
kaist_pref = []

for i in range(1, n+1):
    temp = [i]
    for dist in range(1,n):
        for j in range(n, 0, -1):
            if abs(i-j) == dist:
                temp.append(j)
    kaist_pref.append(temp[::-1])

def stable_marriage(men_preferences, women_preferences):
    n = len(men_preferences)
    free_men = list(range(n))
    women_partners = [None] * n 
    men_next_proposal = [0] * n 
    men_partners = [None] * n
    
    women_rankings = []
    for wp in women_preferences:
        ranking = [0] * n
        for i, man in enumerate(wp):
            ranking[man - 1] = i
        women_rankings.append(ranking)
    
    while free_men:
        man = free_men.pop(0)
        woman_index = men_next_proposal[man]
        woman = men_preferences[man][woman_index] - 1
        men_next_proposal[man] += 1
        
        if women_partners[woman] is None:
            women_partners[woman] = man
            men_partners[man] = woman
        else:
            current_partner = women_partners[woman]
            if women_rankings[woman][man] < women_rankings[woman][current_partner]:
                women_partners[woman] = man
                men_partners[man] = woman
                free_men.append(current_partner)
            else:
                free_men.append(man)
    
    return [w + 1 for w in men_partners]

matches = stable_marriage(person_pref, kaist_pref)
print(*matches)