[백준 파이썬] 1713 후보 추천하기

 문제

주어진 사진틀의 개수만큼 사진을 넣을 수 있고, 기존 사진이 들어오면 점수가 증가, 사진틀에 없는 사진이 들어오면 기존 사진틀의 사진 중 가장 낮은 점수를 가진 사진이 빠지고 새로운 사진이 들어오는 방식이다.
점수가 같아 빠지는 사진이 여러장일 경우 가장 오래된 사진이 빠진다.

 

---

풀이

처음엔 스택을 사용하려 했으나 저장해야할 배열이 사진틀, 점수, 투표된 인원 3가지이기 때문에 배열로 구현하였다.

먼저 크게 2가지로 구분하였는데, 넣으려는 후보의 사진이 이미 사진틀에 있는 경우와 없는 경우로 나누었다.

이미 사진이 있는경우 배열에서 해당사진의 위치를 찾아 점수를 +1 하였다.

if vote[i] in pic: #사진틀에 이미 넣으려는 사진이 있을경우
        for j in range(len(pic)):
            if vote[i] == pic[j]:
                score[j] += 1

 

사진틀에 넣으려는 후보가 없을경우에는 사진틀이 꽉차있는경우의 조건을 걸었다.

사진틀이 꽉찬 경우에는 오래된 사진(배열에서 앞쪽을 의미)를 제거해야 하므로 min(score)을 통해 score의 최소값을 찾고, 배열을 돌며 해당 score을 가진 사진을 제거하였다.

이후 넣으려는 후보를 append하여 구현하였다.

if len(pic) >= N:  # 사진틀 꽉참
            minScore = min(score)
            for j in range(N):
                if minScore == score[j]:
                    del pic[j]
                    del score[j]
                    break
        pic.append(vote[i])
        score.append(1)

---

코드

N = int(input())
count = int(input())
vote = list(map(int, input().split()))
pic = []
score = []

for i in range(count): #투표 수 만큼 반복
    if vote[i] in pic: #사진틀에 이미 넣으려는 사진이 있을경우
        for j in range(len(pic)):
            if vote[i] == pic[j]:
                score[j] += 1
    else:  # 사진틀에 없음
        if len(pic) >= N:  # 사진틀 꽉참
            minScore = min(score)
            for j in range(N):
                if minScore == score[j]:
                    del pic[j]
                    del score[j]
                    break
        pic.append(vote[i])
        score.append(1)


pic.sort()
print(' '.join(map(str, pic)))