[백준] '등수 매기기' 문제 풀이

문제 링크 - https://www.acmicpc.net/problem/2012

2012번: 등수 매기기

---

 

문제 설명

n명에게 각각 예상 등수값을 입력받고, 그 값들을 토대로 불만족 지수가 최소로 나오도록 구성하여 불만족 지수의 최소값을 출력

불만족 지수란 예상 등수가 1등이고, 실제 순위 구성 후 등수가 3등인 경우 (|1-3|)으로 2의 값이 됨

(n의 범위는 1이상 500,000이하)

 

풀이법 구상

예상 순위보다 실제 순위가 높든 낮든 무관하게 그 차이값만큼이 불만족 수치가 됨

최대한 예상 순위가 실제 순위가 되도록 해야하므로 정렬 후 각 예상 순위값을 돌며 실제 순위와의 차이값을 구해야함

정렬 + 반복문이 필요함

-> 스위프트 기본 정렬 메소드의 시간복잡도 - O(n log n)

-> 반복문 시간 복잡도 - O(N)

-> 동시에 일어나지 않고 정렬 후 반복문 돌게됨

 

코드 구현 (스위프트 사용)

import Foundation

func solution(_ arr: [Int]) -> Void {
    var sum = 0
    let temp = arr.sorted()
    for i in 1...arr.count { sum += abs(i - temp[i-1]) }
    print(sum)
}

var arr: [Int] = []
let cnt = Int(readLine()!)!
for _ in 0..<cnt { arr.append(Int(readLine()!)!) }

solution(arr)