[백준/Python] 1713 후보 추천하기

 

📌문제 탐색하기

• 월드초 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의해 정해진 수만큼 선정
• 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보 수만큼 만듦
• 추천 학생을 사진틀에 게시하고 추천 횟수를 표시하는 규칙
  • 추천을 시작하기 전 모든 사진틀은 비어있음
  • 특정 학생을 추천하면, 추천받은 학생의 사진이 사진틀에 게시
  • 비어있는 사진틀이 없다면, 추천받은 횟수가 가장 적은 학생 사진을 삭제하고 새롭게 추천받은 학생 사진 게시
  • 추천 받은 횟수가 가장 적은 학생이 두 명 이상인 경우, 그 중 가장 오래된 사진 삭제
  • 이미 게시된 학생이 추천받으면 추천 횟수만 증가
  • 게시된 사진이 삭제되면 해당 학생의 추천 횟수는 0으로 초기화
• 사진틀의 개수 N(1 ≤ N ≤ 20)과 전체 학생의 추천 결과(총 추천 횟수 1,000번 이하)가 순서대로 주어졌을 때 최종 후보 구하기

추천을 받을 때마다 사진틀에 학생을 등록한다. 이때, 사진틀에는 학생의 번호와 추천 횟수, 마지막으로 몇번째로 추천받았는지를 함께 기록한다. 매 추천 시에 학생의 자리가 있는지 없는지 사진틀을 한번씩 순회하여 확인하고 학생의 자리가 없다면 정렬을 통해 삭제할 학생을 구하면 사진틀의 개수가 최대 20개이고 최대 추천 횟수가 1000번으로 연산 횟수가 최대 1000 * 20 * 20log20이므로 충분히 시간 내에 풀이가 가능하다.

 

 

---

📌코드 설계하기

1. 사진틀의 개수 N을 입력받는다.
2. 총 추천 횟수 counts를 입력받는다.
3. 추천받은 학생들의 번호를 리스트 recomendations로 입력받는다.
4. 사진틀을 리스트 photos으로 정의한다.
5. recomendations의 요소를 하나씩 돌면서, 아래의 규칙대로 사진틀을 업데이트한다.
   1. 사진틀의 모든 요소를 순회하면서, 현재 추천 받은 학생의 번호와 일치하는 요소가 있는지 확인한다.
   2. 사진틀에 이미 있는 학생이 추천받았다면, 해당 학생의 추천횟수를 업데이트한다.
   3. 사진틀에 없는 학생이 추천받았고, 아직 photos의 길이가 N이 아니라면, photos에 [추천횟수, 추천 받은 시기, 학생번호]를 추가한다.
   4. 사진틀에 없는 학생이 추천받았고, photos의 길이가 이미 N이라면, photos를 추천횟수가 적고, 추천 받은 지 오래된 순으로 정렬해 가장 앞에 오는 학생의 자리를 새로 추천 받은 학생의 정보로 업데이트한다.
6. 모든 추천이 끝나면 학생 번호 기준 오름차순 정렬하여 번호만 출력한다.

 

---

📌 시도 회차 수정 사항

• 1회차
  • 사진틀에 이미 있는 학생이 추천받았을 경우, 추천 횟수 뿐만 아니라 추천 받은 시기를 같이 업데이트해서 일부 테스트케이스에서 오답 판정을 받았다.

 

---

📌정답 코드

N = int(input())
counts = int(input())
recomendations = list(map(int, input().split()))

photos = []
for i in range(counts):
    student_num = recomendations[i]
    
    for idx in range(len(photos)):
        if photos[idx][2] == student_num:
            photos[idx][0] += 1     
            break
    else:
        if len(photos) < N:
            photos.append([1, i, student_num])
        else:
            photos.sort(key=lambda x: (x[0], x[1]))
            photos[0] = [1, i, student_num]

photos.sort(key=lambda x:x[2])
print(*[photo[2] for photo in photos])