Audit evidence consolidation

한 회계법인은 여러 지점의 회계감사를 진행하고 있다.

각 지점에서는 감사 과정에서 발견된 증빙 자료를 본사 서버로 전송한다.

증빙 자료는 중요도 점수로 관리되며, i번째 자료의 중요도는 Ai이다.

감사팀은 자료를 분석하기 쉽도록 중요도가 오름차순으로 정렬된 상태에서, 중요도가 같은 자료는 하나의 그룹으로 합치려고 한다.

합쳐진 각 중요도 그룹에 대해 다음 값을 계산한다.

(해당 중요도) × (그 중요도를 가진 자료의 개수)

그리고 모든 그룹의 값을 합산한 결과를 감사 증빙 통합 점수라고 정의한다.

주어진 N개의 증빙 자료의 중요도가 주어질 때, 감사 증빙 통합 점수를 구하여라.

첫째 줄에 증빙 자료의 개수 N이 주어진다.

둘째 줄에 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.

감사 증빙 통합 점수를 출력한다.

• 1 ≤ N ≤ 300,000
• 1 ≤ Ai ≤ 10^9

7
3 1 3 2 1 3 2

10
5 5 7 2 7 7 2 1 5 1

15

42

각 중요도의 개수는 다음과 같다.

따라서 감사 증빙 통합 점수는

2 + 4 + 9 = 15

이다.

각 중요도의 개수는 다음과 같다.

따라서 감사 증빙 통합 점수는

2 + 4 + 15 + 21 = 42

이다.

같은 중요도를 가진 자료의 개수를 세어야 한다.

해시 맵(딕셔너리)을 이용하여 각 중요도의 등장 횟수를 계산한 뒤,

중요도 × 등장 횟수

를 모두 더하면 된다.

자료를 한 번만 순회하여 빈도를 계산하고, 이후 딕셔너리를 순회하여 답을 구할 수 있다.

시간 복잡도는

O(N)

이며,

추가 공간 복잡도는 서로 다른 중요도의 개수를 M이라 할 때

O(M)

이다.

import sys
from collections import defaultdict

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

count = defaultdict(int)

for x in A:
    count[x] += 1

answer = 0

for value, freq in count.items():
    answer += value * freq

print(answer)