BOJ 20009 형곤이의 소개팅

https://www.acmicpc.net/problem/20009
시간 1초, 메모리 512MB

input :

• N (1 ≤ N ≤ 200)
• N명의 남자 이름
• N명의 여자 이름
• N개의 줄에 남자가 선호하는 사람의 이름
• N개의 줄에 여자가 선호하는 사람의 이름

output :

• 매칭한 결과를 남자와 여자의 이름에 공백을 두어 출력

조건 :

• 이 소개팅은 성공률이 100%

• 최적의 짝이란 임의의 남녀 쌍에 대하여 서로가 현재 파트너보다 우선순위가 높은 경우가 없는 것을 말한다

---

SMP 알고리즘을 토대로 구성하였다.

while문에서 사용하는 2개의 조건문을 구성하는 데 계속 타이핑을 잘못 해놓고 확인을 못해서 시간을 많이 허비했다. 과거 알고리즘 강의에서 했던 문제를 복기하는 듯했다.

정답 리스트 ans_girl에는 짝 지은 남자의 이름을 저장해서 2가지를 확인한다.

남자의 기준
1. 상대방 여자가 짝 지은 상대가 없는 경우 자신이 그 곳에 들어간다.
2. 여자의 선호도 기준으로 자리를 얻을 수 있는지 확인한다.

import sys
from collections import deque

n = int(sys.stdin.readline())
pref_boy, pref_girl, ans_girl = dict(), dict(), dict()

boy_name = list(sys.stdin.readline().split())
girl_name = list(sys.stdin.readline().split())

for item in boy_name:
    pref_boy[item] = dict()
for item in girl_name:
    pref_girl[item] = dict()
    ans_girl[item] = 0

for _ in range(n):
    temp = list(sys.stdin.readline().split())

    for i in range(1, len(temp)):
        pref_boy[temp[0]][temp[i]] = i

for _ in range(n):
    temp = list(sys.stdin.readline().split())

    for i in range(1, len(temp)):
        pref_girl[temp[0]][temp[i]] = i

boy_name = deque(boy_name)
while boy_name:
    boy = boy_name.popleft()

    for key in pref_boy[boy].keys():
        if ans_girl[key] == 0:
            ans_girl[key] = boy
            break

        occupy = ans_girl[key]
        if pref_girl[key][occupy] > pref_girl[key][boy]:
            boy_name.append(occupy)
            ans_girl[key] = boy
            break

for item in ans_girl.keys():
    print(ans_girl[item], item)