시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 260 | 110 | 80 | 39.024% |
연애가 하고싶은 형곤이는 소개팅을 통해서 자신의 짝을 만나려고 한다. 형곤이의 소개팅에는 특별한 규칙이 있다.
남자와 여자가 각각 N명씩 만나서 서로가 만나고 싶은 순위를 정해서 최적의 짝을 만들게 된다. 일반적인 소개팅이라면 성공 확률이 높지 않지만 이 소개팅은 성공률이 100%이다. 모두에 대하여 서로가 만족할 수 있는 최적의 짝을 정해준다. 최적의 짝이란 임의의 남녀 쌍에 대하여 서로가 현재 파트너보다 우선순위가 높은 경우가 없는 것을 말한다. 예를 들어 남자와 여자가 각각 2명이라고 할 때 다음의 경우를 생각해보자.
남자와 여자가 각각 2명씩 소개팅에 참여한다. 남자1은 [여자1, 여자2] 남자2는 [여자2, 여자1], 여자1은 [남자1, 남자2], 여자2는 [남자2, 남자1] 순서로 만나고 싶어한다고 하면 남자1-여자2, 남자2-여자1을 매칭하는 것은 최적의 짝이 아니다. 왜냐하면 남자1과 여자1은 현재 자신의 파트너보다 서로를 더 선호하기 때문이다. 형곤이가 소개팅에서 최적의 짝을 찾는 프로그램을 작성해보자. 최적의 짝이 여러 개인 경우, 아무거나 구하면 된다.
첫 번째 줄에는 남자와 여자의 수를 의미하는 N (1 ≤ N ≤ 200)이 주어진다.
두 번째 줄과 세 번째 줄에는 각각 N명의 남자, N명의 여자의 이름이 주어진다.
이름은 알파벳 소문자와 숫자로 이루어져 있으며 4글자 이상 10글자 이하이다.
4번째 줄부터 N + 3번째 줄까지는 각각 N+1명의 이름이 주어진다. 첫 번째는 남자의 이름이고, 그 후부터는 모든 여자의 이름이 해당 남자가 선호하는 순서대로 주어진다.
N + 4번째 줄부터 2N + 3번째 줄까지는 각각 N+1명의 이름이 주어진다. 첫 번째는 여자의 이름이고, 그 후부터는 모든 남자의 이름이 해당 여자가 선호하는 순서대로 주어진다.
모든 이름은 유일하며 서로 다른 성별 간에도 같은 이름이 존재하지 않는다.
두, 세 번째 줄에서 나오는 남자, 여자 이름의 순서와 그 이후에 나오는 남자, 여자 이름의 순서는 관련이 없다.
N개의 줄에 각각 남자와 여자를 매칭한 결과를 남자와 여자의 이름에 공백을 두어 출력하자.
출력하는 순서는 상관이 없다.
3 hyeyoo doby yepark sunhpark soohchoi yomoon hyeyoo soohchoi sunhpark yomoon doby yomoon soohchoi sunhpark yepark sunhpark soohchoi yomoon sunhpark yepark hyeyoo doby soohchoi doby hyeyoo yepark yomoon hyeyoo doby yepark
doby yomoon hyeyoo soohchoi yepark sunhpark
University > 충남대학교 > 제4회 생각하는 프로그래밍 대회 I번