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

1713번 후보 추천하기

 

 

 

 

🎮 문제접근 방법

 

- 사진이 올라간 경우에는 1추가

 

- 사진을 새로 올려야 하는 경우

1) 사진 틀이 꽉 차지 않았다면 1로 지정

 

2) 사진 틀이 꽉 차있는 경우 사진의 min 값을 찾아 제거한뒤 추가

    2-1) min값이 2개이상일 경우, 오래된 값을 찾아 제거하고 추가

 

 

저는 위와 같이 로직을 짜봤습니다.

 

리스트와 딕셔너리 중에 어떤걸 사용할지 고민했는데요.

 

후보의 숫자와 추천수를 같이 짝지우기 위해서 저는 딕셔너리를 선택했습니다.

 

가능한 후보 숫자(100) 리스트를 새로 만들어서 거기서 count 하는 방식도 가능하더라고요!

 

 

 

 

 

🎈 주의할 점

 

 

저는 오래된 값을 처음 입력받은 투표한 리스트에서 세고, 나가게 되는 경우는 값을 -1로 바꿔줘서 업데이트를 하는 방식으로 구현했습니다.

 

그래서 사진 틀에서 제외 될때는 다시 해당 값을 찾아 제거해야 하는데요. 2개면 2개 모두 찾아 -1로 바꿔줘야 하는데

하나만 찾아서 바꿔주는 실수를 했습니다. 

 

 

=>  조건이나 값 변환할때 유념해서 하기!

 

 

 

  

N = int(input())
total_voted = int(input())
voted = list(map(int, input().split()))

candidates = {}
for i in range(total_voted):
    # 사진이 올라간 경우는 1 추가
    if candidates.get(voted[i]):
        candidates[voted[i]] += 1
    # 사진을 새로 올려야 되는 경우
    else:
        # 만약 이미 사진올리는 틀이 꽉찼을 때
        if len(candidates) == N:
            min = total_voted
            # 작은 값을 구한다.
            for idx in candidates:
                if candidates[idx] < min:
                    min = candidates[idx]
                    remove = idx
                # 동일한 작은 값이 있을 때
                elif candidates[idx] == min:
                    # 순서를 따져본다.
                    for j in range(i):
                        # 이전값이 순서가 먼저 발생할 경우
                        if voted[j] == remove:
                            break
                        # 새로운 값이 순서가 먼저 발생할 경우
                        if voted[j] == idx:
                            min = candidates[idx]
                            remove = idx
                            break
            # 다음 순서 판별시 걸리지 않도록-1 처리
            for _ in range(min):
                voted[voted.index(remove)] = -1
            # 딕셔너리에서도 삭제
            del (candidates[remove])
        # 사진 틀에 추가
        candidates[voted[i]] = 1

ans = sorted(candidates)
print(*ans)

 

 

 

 

🎁 아래 코드는 다른 분들의 풀이를 살피다가 신박한? 풀이라고 생각되서 참고하여 다시 짠 코드입니다.

 

오래된 순서를 파악하기위해 아예 값에다가 처리를 했더라고요.

 

추천횟수는 최대 1000회 이하라는 것을 이용하여

 

추천이 될때마다 값에다가 0.00001 을 빼줌으로써 자연스레 오래된 값일수록 더 작아지게 됩니다.

 

그러므로 똑같이 2번 추천받았더라도 최신값이 더 크고, 오래된 값이 작을 수 밖에 없도록 만들어 따로 처리를 할 필요없도록 하는 것도 시간을 줄이는 좋은 방법이었어요!

 

 

 

N = int(input())
total_voted = int(input())
voted = list(map(int, input().split()))

candidates = {}
for i in range(total_voted):
    if candidates.get(voted[i]):
        candidates[voted[i]] += 1
    else:
        # 이미 사진올리는 틀이 꽉찼을 때
        if len(candidates) == N:
            min = total_voted
            # 작은 값을 구한다.
            for idx in candidates:
                if candidates[idx] < min:
                    min = candidates[idx]
                    remove = idx
            # 딕셔너리에서도 삭제
            del (candidates[remove])

        # 사진 틀에 추가
        candidates[voted[i]] = 1
    
    # 오래된 순서를 값으로 처리    
    for n in candidates:
        candidates[n] -= 0.00001

ans = sorted(candidates)
print(*ans)

 

 

 

 

 

 

 

www.acmicpc.net/problem/1713

1713번: 후보 추천하기