#1713 후보 추천하기

출처: https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

 

문제에서 친절하게 알고리즘 설계도를 줬다. 해당 상세 구현 설명을 기준으로 문제를 조금 재해석해서 내 맞춤으로 다시한번 수정해 보았다.

 

먼저 문제는 학생의 사진을 게시할 수 있는 정해진 사진틀이 있고 추천할때마다 항상 추천한 그 학생의 사진은 사진틀에 걸려야 한다. 이 과정에서 문제와같이 처음 사진틀이 비어있을경우, 사진틀이 다 차있는데 새로운 학생을 추천할 경우, 사진틀에 있는 학생을 추천할 경우로 나뉘어지고 그밖에 세부 예외조건이 있다. 문제를 풀면서 실수를 한 부분이 있었다.사진틀이 다 채워진 경우에 추천한 학생으로 사진틀을 무조건 바꿔서 틀렸었다. 만약 추천한 학생이 사진틀에 있는경우 사진틀은 교체되지 않고 추천횟수만 증가시키는것을 적용 시켜야 하는데 이 과정을 맨 처음 사진틀이 다 채워지지 않는 경우에만 적용하여서 틀린것이였다. 위의 문제에 4번 조항인데 한줄만 적혀 있어서 그대로 잘라내기로 처음에 붙여넣기를 해서 한번만 적용 했다가 실수를 한 것 같다. 

 

코드 구현은 위에 나와있는 문제 순서 그대로 다음과 같이 풀이를 하여 적용시켰다.

 

알고리즘 순서

학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.

어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.

 

현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.

사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

 

비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. (실수한 부분 이곳에도 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다를 적용 했어야 했다.)

 

이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 게시된 지 가장 오래된 사진을 삭제한다.

 

이런 순서로 문제를 해결하였다.