1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 각 사람의 예상 등수가 주어졌을 때, 불만도의 합을 최소로 하는 프로그램을 작성하시오.
# 틀린코드
시간 초과........날만하다. min도 O(N)이고 index도 O(N)인데 같이쓴데다가 반복문도 두번씀. pop도 맨끝 아니니까 거의 O(N) 최소 O(N^3) 너무 비효율적인 코드다. 다시 생각해보자. 실제 등수와 예상 등수의 뺀 값이 최소가 되려면 차이가 적어야 한다. 큰 수에서 작은 수, 작은 수에서 큰 수를 빼면 절댓값이 커진다. 그럼 작은 수랑 작은 수를 빼고, 큰 수랑 큰 수를 뺀다? 그럼 정렬한다음 각각 빼면 되는 거 아닌가?
import sys
input = sys.stdin.readline
N = int(input())
ranks = [i for i in range(1, N+1)]
expectRanks = []
count = 0
for _ in range(N):
expectRanks.append(int(input()))
for i in range(N):
minRanks = []
for j in ranks:
minRanks.append(abs(expectRanks[i]-j))
count += min(minRanks)
ranks.pop(minRanks.index(min(minRanks)))
print(count)# 정답코드
맞았다. 그럼 처음부터 정렬을 떠올리지 못한 이유를 생각해보자.
처음 코드를 짰을 때도 최솟값을 만들기 위해 뺀 절대값이 0이나 1이 되는 경우를 먼저 제외하는 경우도 생각해보았다. 0이나 1이 되는 경우를 리스트를 다 돌면서 찾을 생각을 했다. 그래서 시간초과가 난 것이다. 범위가 정해져 있으니까 그냥 정렬해서 각각 빼주면 0이 되는 경우는 자연스럽게 0이 된다.
그리디 알고리즘은 항상 아이디어 싸움인 것 같다. 아이디어를 떠올리지 못하면 복잡한 길로 가게 되고, 그 길은 결국 막혀버린다. 아이디어를 떠올리면 코드는 이렇게 간단할 수 없다. 많이 풀어서 경험적으로 알아가는 수 밖에 없는 것 같다. 앞으로도 꾸준히 화이팅 !
import sys
input = sys.stdin.readline
N = int(input())
ranks = [i for i in range(1, N+1)]
expectRanks = []
count = 0
for _ in range(N):
expectRanks.append(int(input()))
expectRanks.sort()
for i in range(N):
count += abs(ranks[i]-expectRanks[i])
print(count)