채용박람회 timer 1s memory 256MB

다양한 기업과 많은 지원자들이 참여한 대규모 공개 채용 이벤트가 진행되었다. 

마침내 엄청난 경쟁을 뚫고 올라온 N명의 지원자들이 M개의 기업에 입사할 수 있는 기회를 얻었다.

이벤트 진행자는 설문을 통해 각 기업으로부터 지원자 선호 순위와 채용 인원수를 수집했고,

각 지원자로부터 기업 선호 순위와 입사를 희망하는 기업 수를 수집했다.

이 정보를 이용해 기업과 지원자들을 매칭 하려고 한다.

아래 표 2개는 각각 기업과 지원자의 설문조사 내용을 나타낸다.

기업의 이름은 알파벳 대문자로, 지원자의 이름은 알파벳 소문자로 나타낸다.

첫 번째 표는 각 기업이 선호하는 지원자의 순위와 채용하고자 하는 인원수를 나타낸다.

> 의 오른쪽에 있을수록 선호도가 낮음을 의미한다.

기업     지원자에 대한 선호도       채용 인원수

A        f > a > b > d > e > c       2

B        c > e > b > d > f > a       2

C        e > c > f > a > d > b       2

두  번째 표는 각 지원자가 선호하는 기업의 순위와 입사하고자 하는  기업의 수를 나타낸다.

어떤 지원자의 입사 희망 기업 수가 1일 경우, 선호도 상위 1의 기업에만 입사할 의지가 있음을 나타낸다.

지원자      기업에 대한 선호도        입사 희망 기업 수

a           B > A > C              1

b           B > A > C              3

c           B > C > A              2

d           A > B > C              3

e           B > C > A              3

f            A > B > C              2

다음 과정을 따라 기업과 지원자를 매칭한다.

1단계. 지원자는 거절당하지 않았던 기업 중에서 자신의 선호도가 가장 높은 기업 한 곳을 지원한다.

      입사 희망 기업으로부터 모두 거절당하면 지원을 중단한다.

2단계. 기업은 채용 인원수를 넘지 않는 한도 내에서 선호도가 높은 순서대로 지원자를 잠정 선택한다.

      선택되지 못한 지원자들은 거절당한다.

3잔계. 거절당한 지원자들 중에서 다른 기업에 지원할 지원자가 있다면 1단계부터 반복하고,

      없다면 현재의 잠정 선택을 최종 매칭으로 결정한다.

아래 그림은 기업과 지원자를 매칭하는 과정이다.

총 4라운드를 거치며, 파란색 기울임 문자는 기업이 잠정 선택한 지원자를 나타낸다.

화살표는 거절당한 지원자가 다음 라운드에 지원하는 기업을 가리킨다.

1라운드에서는 모든 지원자가 각자 가장 선호하는 기업에 지원한다. 

A기업은 채용인원이 2명이기 때문에 지원자 2명을 잠정 선택한다.

B기업은 채용인원이 2명인데 4명이 지원을 했기 때문에 

B기업이 선호하는 c, e를 잠정 선택하고 a, b는 거절한다.

거절당한 a는 입사 희망 기업이 오직 B이기 때문에 더 이상 다른 기업에 지원하지 않는다.

2라운드에서는 B에게 거절당했던 b가 B다음으로 선호하는 A기업에 지원한다.

A기업은 3명의 지원자 중 선호도가 높은 f, b를 잠정 선택하고 d는 거절한다.

3라운드에서는 d가 B기업에 지원한다. 

B기업은 3명 중 선호도가 높은 c, e를 잠정 선택하고 d는 거절한다.

4라운드에서는 d가 C기업에 지원한다. 

C기업은 지원자의 수가 채용인원 수 이하이기 때문에 d를 잠정 선택한다.

더 이상 다른 기업에 지원할 지원자가 없기 때문에 매칭을 종료한다.

매칭 결과, A기업에는 b, f지원자가, B기업에는 c, e지원자가, 

C기업에는 d지원자가 매칭 되었다.

기업별 지원자에 대한 선호리스트와

지원자별 기업에 대한 선호리스트를 입력받아

기업별 선택된 지원자를 구하여 출력하는 프로그램을 작성하시오.​