[BOJ] 1713번 후보 추천하기 (C++)

문제 링크 (https://www.acmicpc.net/problem/1713)

1713번: 후보 추천하기

추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시해야한다.

입력 : 사진틀의 개수와 전체 학생의 추천 결과(추천받은 순서대로)

출력 : 최종 후보

 

map을 사용하여 해결한 문제!

map <int, pair<int, int>> m; (추천 받은 학생, (추천 수, 들어온 시기)) 

 

- 비어있는 사진틀이 있다면?

  insert 함수 실행 

  -> 해당 학생이 이미 사진틀에 존재한다면 해당 학생의 추천 수 증가

  -> 존재하지 않는다면 추천 수는 1, 들어온 시기 설정

 

- 비어있는 사진틀이 없다면? 

  erase 함수 실행

  -> 해당 학생이 이미 사진틀에 존재한다면 해당 학생의 추천 수 증가

  -> 존재하지 않는다면 

      -> m을 추천 순으로 정렬

      -> 추천 횟수가 가장 적은 학생이 한 명이라면? 그 학생을 사진틀에서 제거

      -> 추천 횟수가 가장 적은 학생이 두 명 이상이라면? 그 학생들을 들어온 시기 순으로 정렬 후 가장 먼저 들어온 학생을 사진틀에서 제거

 

- m의 first를 순서대로 출력 (map은 자동으로 오름차순 정렬이므로 바로 출력하면 됨)

---

[소스코드]

---

2021-07-17

Silver 2

알고리즘 분류

   - 구현