[실버 1] 백준 1713 - 후보 추천하기 (파이썬)

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

풀이

• 사진틀이 N개 있다.
• 총 M명의 추천이 차례로 주어진다.
• 이미 사진틀에 있는 학생은 추천 수만 증가한다.
• 사진틀에 자리가 없으면,
  • 추천 수가 가장 적은 사람을 사진틀에서 제거
  • 만약 추천 수가 같으면 가장 오래된 사람을 제거
• 마지막에 사진틀에 걸려 있는 학생 번호를 오름차순 출력

count = [0] * 100  # 학생별 추천 수 (인덱스 = 학생 번호 - 1)
last = [-1] * 100  # 학생별 마지막 추천받은 시간 (인덱스 = 학생 번호 - 1)

• 학생 번호는 1 ~ 100까지 가능하다.
• count[i] 는 i번 학생의 추천수를 나타낸다.
• last[i]는 i번 학생이 사진틀에 걸린 시간을 나타낸다.

for i in range(M):
    C[i] -= 1  # 학생 번호를 0부터 시작하게 조정
    count[C[i]] += 1  # 추천 수 증가

• 추천을 받으면 count를 1증가한다.

if last[C[i]] != -1:
    continue

• 이미 사진에 걸려 있는 경우는 추천수만 증가시키고 넘어간다.

picture = 0
for j in range(100):
    if last[j] != -1:
        picture += 1

• 사진틀이 꽉 찼으면 탈락자를 찾는다. 위 코드는 현재 사진틀에 몇 명 걸려있는지 센다.

if picture == N:
    min_count = 1e9
    min_last = 1e9
    who = -1
    for j in range(100):
        if last[j] != -1:
            if min_count > count[j]:
                min_count = count[j]
                min_last = last[j]
                who = j
            elif min_count == count[j] and min_last > last[j]:
                min_last = last[j]
                who = j

• 추천수가 가장 적은 학생을 찾고, 만약 동점이면 더 오래된 학생을 찾는다.

count[who] = 0
last[who] = -1

• 해당 학생을 탈락시킨다.

last[C[i]] = i

• 이 시점에 새로 등록되었으니까, 추천받은 시간을 저장한다.

코드

# 백준 1713 - 후보 추천하기
# 분류 : 구현

N = int(input())
M = int(input())
C = list(map(int, input().split()))

count = [0] * 100
last = [-1] * 100

for i in range(M) :
    C[i] -= 1

    # 추천
    count[C[i]] += 1

    if last[C[i]] != -1 :
        continue

    picture = 0
    for j in range(100) :
        if last[j] != -1 :
            picture += 1
    
    if picture == N :
        # 탈락
        min_count = 1e9
        min_last = 1e9
        who = -1
        for j in range(100) :
            if last[j] != -1 :
                if min_count > count[j] :
                    min_count = count[j]
                    min_last = last[j]
                    who = j
                elif min_count == count[j] and min_last > last[j] :
                    min_last = last[j]
                    who = j

        count[who] = 0
        last[who] = -1
    
    # 추기
    last[C[i]] = i

for i in range(100) :
    if last[i] != -1 :
        print(i + 1, end = " ")