[백준] 12022 짝

Backjoon

해설

gale-shapley 알고리즘을 통해 풀이할 수 있다.

코드

import sys
input = sys.stdin.readline

N = int(input())
men_pref, women_pref = [], []
for pivot in (men_pref, women_pref):
    for _ in range(N):
        pivot.append(list(map(int, input().split())))

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(men_pref, women_pref)
for match in matches:
    print(match)