[백준 JAVA] 1758 알바생

1758 알바생

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

문제설명

그리디 알고리즘을 사용하여 알바생의 최대 시급 계산

 

• 각 알바생에게 지급할 시급은 그 알바생의 순서에 따라 조정된다.
• 시급은 내림차순으로 정렬된 후, 시급이 감소하는 순서로 지급된다.
• 각 알바생이 받을 수 있는 최대 시급을 계산하여 총 시급을 계산한다.

 

접근방식

O(n log n) 시간복잡도

 

입력된 시급만큼 배열에 저장하고, 정렬한다.

배열의 정렬은 O(n log n)의 시간복잡도를 가진다.

문제 조건 분석 과정

 

1. 첫번째 줄에 알바생의 수 n이 주어진다.

2. 다음 n 줄에 각 알바생의 시급이 주어진다.

 

사용된 자료구조

• Arrays.sort(arr, Collections.reverseOrder()):
  • 배열을 내림차순으로 정렬한다

전체코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Integer[] arr = new Integer[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        //배열을 내림차순으로 정렬
        Arrays.sort(arr, Collections.reverseOrder());

        //계산결과를 저장
        long sum = 0;
        //인덱스 값
        int z = 0;

        for (int i = 0; i < n; i++) {
            //z를 뺀 값이 0보다 큰 경우에 sum에 추가
            if (arr[i] - z > 0) {
                sum += arr[i] - (z++);
            } else {
                break;
            }
        }

        sb.append(sum);
        System.out.print(sb.toString());

        br.close();
    }
}