[BOJ][⚪2][백준#01713] 후보 추천하기
작성:
업데이트:
카테고리: BOJ Silver II
태그: BOJ, BOJ Silver, Failed, PS, Python
문제 출처
문제
월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.
학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.
입력
첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.
출력
사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.
예제
입력
3
9
2 1 4 3 5 6 2 7 2
출력
2 6 7
My Sol
# 사진틀 개수 N 투표 횟수 T
N = int(input())
T = int(input())
# 결과 배열 result 투표 기록 배열 votes 학생 별 득표 수 scores
result = []
cnt = 0
votes = list(map(int, input().split()))
scores = [0] * (T+1)
for v in votes:
flag = 0
scores[v] += 1
for p in result:
if v == p:
flag = 1
continue
if flag == 1:
continue
# 꽉 찬 경우
if cnt == N:
# 변수 초기화
min_i = result[1]
min_v = scores[result[1]]
# 반복 진행
for s in result[1:]:
if min_v > scores[s]:
min_i = s
min_v = scores[s]
# 최하 득표 / 가장 오래된 후보 제거
result.remove(min_i)
cnt -= 1
scores[min_i] = 0
# 후보 추가
result.append(v)
cnt += 1
for i in range(N-1, 0, -1):
for j in range(i):
if result[j+1] < result[j]:
result[j], result[j+1] = result[j+1], result[j]
print(result)
결과
틀렸습니다.
My Sol B : 함수 사용
# 사진틀 개수 N 투표 횟수 T
N = int(input())
T = int(input())
# 결과 배열 result 투표 기록 배열 votes 학생 별 득표 수 scores
result = []
votes = list(map(int, input().split()))
scores = [0] * (T+1)
for v in votes:
scores[v] += 1
if v in result:
continue
# 꽉 찬 경우
if len(result) == N:
min_p = result[0]
min_v = scores[min_p]
for k in result:
if min_v > scores[k]:
min_p = k
min_v = scores[k]
result.remove(min_p)
scores[min_p] = 0
# 후보 추가
result.append(v)
print(sorted(result))
알고리즘을 배우면서 내장함수를 사용하지 않고, 알고리즘적으로 풀어보려 했는데 너무 풀리지 않아 함수를 사용해봤다.
결과
틀렸습니다.
모범답안
너무 풀리지 않아 인터넷 블로그를 참조했다.
# 사진틀 개수 N 투표 횟수 T
N = int(input())
T = int(input())
votes = list(map(int, input().split()))
# 후보이름 : [추천수, 들어온 순서]
photo = {}
for i in range(T):
# 이미 등록된 후보
if votes[i] in photo:
photo[votes[i]][0] += 1
# 사진틀에 없던 후보
else:
if len(photo) < N: # 사진틀이 덜 찼다면
photo[votes[i]] = [1, i] # 현재 인덱스를 함께 저장
else:
# photo 딕셔너리의 아이템을 득표수로 먼저 정렬, 같다면 index 순으로 정렬
del_lst = sorted(photo.items(), key=lambda x: (x[1][0], x[1][1]))
del_key = del_lst[0][0] # 정렬 후 가장 처음 있는 값을 del_key로 지정
del(photo[del_key]) # photo딕셔너리에 해당 key를 가진 항목 제거
photo[votes[i]] = [1, i]
ans_lst = sorted(photo.keys())
print(*ans_lst)
접근을 제외한 문법은 아쉬운 부분이 있어서 주석을 달면서 문법을 정리하였다.
이 분은 딕셔너리를 사용했다. 후보자 번호를 key로 하고, [득표수, 등록순서]를 value로 하는 item들의 dictionary이다.
투표 번호 votes[i]가 이미 photo의 있다면 votes[i]를 key로 하는 value의 0번째, 즉 득표수를 1만큼 올려준다.
만약 사진틀에 없던 후보라면 2가지 경우로 나뉘는데, 먼저 사진틀이 덜 찼다면 그냥 득표수 1과 현재 등록 순서 i가 있는 리스트를 value로 하여 votes[i]를 key로 해서 dictionary에 추가하면 되겠다.
반면 사진틀이 꽉 찼다면 한 명을 내보내야 하는데, photo dictionary의 item들을 정렬해야 한다. 이때 득표수를 1순위 기준, 등록 순서를 2순위 기준으로 하여 정렬한다. 정렬은 오름차순으로 정렬되기 때문에 이 정렬 이후 photo dictionary item들의 리스트의 0번째 항목은 photo dictionary item중 득표수가 가장 적으면서도 가장 idx가 작은, 즉 오래된 항목이다.
del_lst[0]은 해당 key와 value를 모두 가지고 있고, key를 0, value를 1로 하기 때문에 del_lst[0][0]은 결국 가장 적은 득표수 중 가장 오래된 후보의 번호이다. 이를 del_key에 할당한다.
photo dictionary에서 del_key를 key로 하는 항목을 del() 함수를 이용해 제거한다. 이후 신규 후보를 추가해주면 되겠다.
마지막으로 photo dictionary의 key 리스트를 정렬하여 출력한다.
나와 달랐던 점은 나는 투표 votes의 각 항목들을 후보 번호로 생각해 이를 통해 처리하려 했으나, 이 방식은 전체 투표 횟수를 range()로 하여 인덱스로 처리하고, 이를 votes[i]처럼 해서 후보 번호를 찾았다는 점이다. 또한 이 인덱스, 즉 등록 순서를 기반으로 하는 딕셔너리를 생각해낸 것도 신박하다고 느꼈다.
댓글남기기