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

 

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

코딩 테스트 문제에서 자주 출현하는 구현 알고리즘이다.

 

보통 1, 2번 문제에 출제되고 긴장하면 말리기 쉬운 문제 유형이니 많이 풀어서 익숙해지는 게 중요한 것 같다.

 

풀이

---

보통 구현 문제는 여러가지 조건을 그대로 구현하면 정답을 맞힐 수 있는 구조로 많이 출제된다.

성급하게 접근하기 보단 문제의 조건을 읽어보고 정리한 뒤에 알고리즘을 설계하는 것을 추천한다.

 

문제의 조건은 다음과 같다.

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

조건을 조금 추려보면, 

1. 추천받은 학생이 사진틀에 존재하는지 확인한다.
2. 존재한다면 해당 사진의 추천수를 증가시키고, 존재하지 않는다면 3번을 수행한다.
3. 사진틀이 비어있다면 사진을 추가해주고, 사진틀이 꽉 차있다면 주어진 조건에 따라 사진을 교체한다.

 

이제 자신있는 컴퓨터 언어로 조건에 맞게 구현을 하면 된다.

 

- 정답 코드

n = int(input())
num = int(input())

def is_in_arr(arr , w):
    for i in arr:
        if i[2] == w:
            return True
    return False

arr = []
who = input().split()
for idx, w in enumerate(who):
    #1
    if is_in_arr(arr, w):
        #2
        for index, var in enumerate(arr):
            if var[2] == w:
                arr[index][0] += 1
                break
    else:
        #3
        if len(arr) < n:
            arr.append([1, idx, w])
        else:
            arr[0] = [1, idx, w]

    arr.sort(key=lambda x: (x[0], x[1]))

arr.sort(key=lambda x:int(x[2]))
for i in range(n):
    if i == n-1:
        print(arr[i][2])
    else:
        print(arr[i][2], end = ' ')

 

결과

---

문제를 얕보다가 5번의 실패를 하고 6번 째 정답을 맞힐 수 있었다.

이 문제가 초등부 알고리즘 경진대회라는게 충격이었다..