BOJ 1713. 후보 추천하기(구현)

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

1713번: 후보 추천하기

1. 사진틀 꽉 차있는 경우, 안 차있는 경우로 나눈다.

2.1 안 차있는 경우에는 

    - 투표된 학생이 존재하는 경우에는 투표수만 증가

    - 그렇지 않은 경우에는 사진틀에 새 학생 추가하기

2.2 차있는 경우

    - 투표된 학생이 존재하는 경우에는 투표수만 증가

    - 그렇지 않은 경우에는 기존 사진틀에 존재하는 학생들 사이에서 최소 투표수 찾아야함

    - 최소 투표수 갖고 있는 학생 여러명인 경우에는 인덱스 먼저 들어가있는 학생을 제거해야함

    - 어차피 사진틀 첫 학생 기준으로 비교 시작하기 때문에 최소 수가 같은 학생의 경우 앞의 학생으로 남게됨(별도 설정X)

    

n = int(input())
v = int(input())
vote_list = list(map(int, input().split()))

stu = [0] * 101
temp = [] #사진틀

for c in vote_list:

    #이미 꽉 차 있는 경우
    if len(temp) == n:
        if c in temp:
            stu[c] += 1
        else:
            mid = temp[0] 
            mc = stu[mid] #학생 번호, 투표 받은 수
            
            for i in temp[1:]:
                if mc > stu[i]:
                    mc = stu[i]
                    mid = i
                
            temp.remove(mid)
            stu[mid] = 0 

            temp.append(c)
            stu[c] += 1
        
    #사진틀 꽉 차있지 않은 경우
    else:
        if c in temp:
            stu[c] += 1
        else:
            temp.append(c)
            stu[c] += 1
        
result = [[i,stu[i]] for i in temp]
result.sort(key = lambda x : x[0])
result = [r[0] for r in result]

print(*result)

 

 

* 다른 분 풀이 비교해보기

- 학생 투표수 리스트를 나는 고정된 길이로 정해버렸는데 사진틀의 학생만 비교하게 된다면 더 효율적인 것 같다.

N = int(input()) # 사진틀 개수
Vote = int(input()) # 총 추천 회수
students = list(map(int, input().split())) # 추천 학생 번호
picture = [] # 사진틀
score = [] # 사진틀 인덱스와 매치해서 추천수 저장할 리스트

for i in range(Vote):
    if students[i] in picture: # 사진틀에 있으면
    	#해당 부분은 나랑 유사 프로세스
        for j in range(len(picture)): 
            if students[i] == picture[j]:
                score[j] += 1 #점수증가
    else: # 사진틀에 없고
        if len(picture) >= N: # 사진틀 꽉차있으면
            for j in range(N):
            	#min, max 함수에서 적용하면 빠른 순서의 변수로 적용된다는 점
                if score[j] == min(score): #가장 작은 점수 찾고
                    del picture[j]
                    del score[j]
                    break #먼저 찾으면 스탑 왜냐면 오래된거일수록 인덱스 앞에 있음
        picture.append(students[i]) #새로운거 뒤에 더해줌
        score.append(1)

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