[n1713] 후보 추천하기 in python

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

1713번: 후보 추천하기

(문제)

추천받은 학생의 사진을 사진틀에 게시하고 추천 받은 횟수를 표시하는 문제

- 비어 있는 사진틀이 있는 경우

- 비어 있는 사진틀이 없는 경우

- 현재 사진이 게시된 학생이 추천받은 경우

총 3가지의 경우의 수가 있다.

 

비어 있는 사진틀이 있는 경우 

: 그냥 사진 추가하면 된다.

 

비어 있는 사진틀이 없는 경우

추천 횟수가 적은 학생의 사진을 삭제한다. 

만약 추천 횟수가 적은 학생이 두 명 이상이라면, 그 중 가장 오래된 사진을 빼고 넣는다.

 

현재 사진이 게시되어 있는 학생이 또 추천을 받은 경우에는

추천 받은 횟수만 증가한다.

 

 

---

(생각)

아무리 생각해봐도 구현인 것 같은 느낌?

set을 이용해야하나 했는데 그렇게 되면 추천수랑 들어온 순서를 담을 수 없어서 패스

dic으로 하게 되면 둘 다 담을 수 있으니까 dict으로 사진틀 구현해보기

 

1. 비어있는 사진틀이 있는 경우
2. 비어있는 사진틀이 없는 경우
    - 추천횟수가 적은 학생의 사진 삭제
    - 그 자리에 새로 들어간다.
       - 만약 추천횟수가 적은 학생이 두명 이상이면, 가장 오래된 사진
         우선순위 : 추천횟수 > 게시순
3. 현재 사진이 게시된 학생이 추천받은 경우 - 추천 받은 횟수만 증가

---

(풀이)

 

1. 사진틀이 꽉 차있지 않은 경우

[1,i] = > [추천수 1, 들어온 순서 (인덱스)]

 

2. 사진틀이 꽉 차있는 경우 **

-> 이 부분이 가장 어려웠다.

 

<사진틀이 꽉 차있는 경우>

lambda 함수 사용하는 게 아직도 익숙치 않다니;

삭제해야하는 사진은 추천수가 적은 학생의 사진, 

만약 추천 받은 횟수가 가장 적은 학생이 두 명 이상이라면, 게시된 지 가장 오래된 사진을 삭제

 

삭제 우선순위 : 1. 추천수 적음 > 2. 가장 오래된 사진

 

sorted함수를 이용해서 위 우선순위를 사진틀을 담고 있는 dictionary에 적용해준다.

sorted(photo_dic.items(),key=lambda x:x[1][0],x[1][1])

>> photo_dic.items()를 하게 되면, [(key,value)] 형태로 반환한다.

 

 

>> lambda x:x[1][0],x[1][1] : value를 기준으로 우선순위를 결정해야 한다.

>> x[0]은 key, x[1]은 value

>> x[1][0]은 추천수, x[1][1]은 들어온 순서

 

따라서 x[1][0]=추천수를 먼저 기준으로 오름차순으로 정렬한다.

만약 추천수가 동일하다면, 게시순번을 기준으로 오름차순으로 정렬한다.

 

내림차순으로 하려면 -를 붙여주면 된다.

ex) lambda x:-x[1][0],-x[1][1]

 

 

3. 현재 사진이 사진틀에 들어가있으면

추천수 +1

 

 

photo_n = int(input())  # n
recommend_n = int(input())  # w
input_list = list(map(int, input().split()))  # num
photo_dic = dict()  # photo

# 키 : 후보자이름, 값 : [추천수,들어온순서]
for i in range(recommend_n):
    if input_list[i] in photo_dic:
        photo_dic[input_list[i]][0] += 1
    else:
        if len(photo_dic) < photo_n:
            # 사진틀 꽉 차지 않았을때
            photo_dic[input_list[i]] = [1, i]
        else:
            # 사진이 꽉 차있을 때
            del_list = sorted(photo_dic.items(), key=lambda x: (x[1][0],x[1][1]))
            del_key = del_list[0][0]
            del (photo_dic[del_key])
            photo_dic[input_list[i]] = [1, i]

answer_list = list(sorted(photo_dic.keys()))
answer = ""
for i in answer_list:
    print(i,end=' ')