[Python] 2012. 등수 매기기

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

2012번: 등수 매기기

 

접근법

• 예상등수와 실제 등수의 차이가 최소가 되어야 한다.
• 따라서 sort된 예상 등수와 1등부터 N등까지의 차를 더한다.

from collections import deque

def input_func():
    N = int(input())
    arr = []
    for i in range(N):
        arr.append(int(input()))
    return sorted(arr)


def solution(arr):
    ans = 0
    for i in range(len(arr)):
        ans += abs(i + 1 -arr[i])
    print(ans)


def main():
    arr = input_func()
    solution(arr)

if __name__ == '__main__':
    main()

---

처음 생각했던 알고리즘의 문제점(틀린이유)

timeout
→ 이미 나온 등수를 다른 숫자로 대체하는 것이 아니라 pop활용해보기
→ input_func을 정렬해서 return하기

from collections import deque

def input_func():
    N = int(input())
    arr = []
    for i in range(N):
        arr.append(int(input()))
    return arr


def solution(arr):
    rank_list = deque(i + 1 for i in range(len(arr)))
    ans = 0
    for pred in arr:
        min_dif = 500000
        min_idx = 0
        for idx, rank in enumerate(rank_list):
            dif = abs(rank - pred)
            if dif < min_dif:
                min_dif = dif
                min_idx = idx
            if dif ==0:
                break
        ans += min_dif
        rank_list[min_idx] = 500001 # 이미 나온 등수 처리
    print(ans)



def main():
    arr = input_func()
    solution(arr)

if __name__ == '__main__':
    main()

 

사용된 알고리즘

그리디 알고리즘, 정렬