[알고리즘|파이썬] 백준 1713 후보 추천하기

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

 

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 128 MB

 

✏️ 구해야 하는 정답

규칙

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

후보의 수(=사진틀의 개수)와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때,

최종 후보의 학생 번호를 증가하는 순서대로 출력하기

 

조건

- 1 ≤ N ≤ 20

- 총 추천 횟수 ≤ 1,000

- 1 ≤ 학생을 나타내는 수 ≤ 100

---

📌 풀이하기 

N = 3

추천 횟수 = 9

추천 받은 학생 = {2, 1, 4, 3, 5, 6, 2, 7 2}

사진틀에 들어갈 학생과 투표 개수를 표현해보면 이러하다.

최종적으로 사진틀에 들어가 있는 학생은 {6, 2, 7} 이고, 사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력해야하기 때문에 정답은 2 6 7이 된다. 

 

✏️ 문제를 어떻게 풀 것인가?

사진 틀에 투표 받은 학생이 없고, 사진 틀이 다 찬 경우 어떤 학생을 제거 해야할 지 정해야한다.

조건에 따라

- 사진틀에 있는 학생 중 투표가 가장 작은 학생을 제거

- 만약 투표수가 중복된 경우 가장 오래된 학생 제거

이 두가지의 조건을 가지고 어떤 학생을 제거할 지 결정해야한다.

 

1. 사진 틀에 있는 학생들의 투표 수를 비교

2. 투표 수가 가장 적은 학생이 있다면 제거

3. 투표 수가 동일한 학생이 2명 이상 있다면 사진 틀의 위치(인덱스) 중 가장 낮은 학생 제거

-> 인덱스가 가장 작다는 것은 가장 오래된 학생이기 때문

 

---

📌 코드 설계하기

i) 사진 틀에 학생이 있는 경우

  투표수 +1

 

ii) 사진 틀에 학생이 없는 경우

  a. 사진틀이 빈 경우

    사진 틀에 추가

    투표수 +1

  b) 사진 틀이 다 찬 경우

    사진틀에 있는 학생 중 투표가 가장 작은 학생을 제거

    만약 투표수가 중복된 경우 가장 오래된 학생 제거

    제거한 학생의 투표수는 0으로 초기화

    사진 틀에 추가

    투표수 +1

 

사진 틀 오름차순으로 정렬 후 출력

 

---

📌 정답 코드

n = int(input())
num = int(input())
candidates = list(map(int, input().split()))
votes = [0] * 101
dq = list()


def find():
    min_idx = float('inf')
    min_votes = float('inf')
    mins = list()
    for idx in range(n):
        d = dq[idx]
        if min_votes > votes[d]:
            min_votes = min(votes[d], min_votes)
            mins.clear()
            mins.append(idx)
            min_idx = idx
        elif min_votes == votes[d]:  # 동일한 투표 개수
            mins.append(idx)
        else:
            continue
    if len(mins) > 1:
        mins.sort()
        return mins[0]
    else:
        return min_idx


for i in range(num):
    if candidates[i] in dq:
        votes[candidates[i]] += 1
    else:
        if len(dq) >= n:
            toDelIdx = find()
            toDel = dq[toDelIdx]
            dq.remove(toDel)
            votes[toDel] = 0
        dq.append(candidates[i])
        votes[candidates[i]] += 1

dq.sort()
for l in dq:
    print(l, end=" ")