[Java]자바 우선순위 큐 응용하기1 -뒤에서부터 생각하면 효과적으로 변하는 경우-

1. 문제

 

N개의 정수들이 있습니다. 이 중 정확히 앞에서부터 K개를 삭제하고 난 후, 남아있는 정수 중 가장 작은 숫자 하나를 제외한 평균을 구한다 했을 때 이 평균값이 최대가 될 때의 값을 구하는 프로그램을 작성해보세요. 단, K는 1이상 N - 2 이하까지만 고려하도록 합니다.

 

아니 쉬운문제 같은데 메모리,시간제한 도저히 안되는데..?

 

2. 풀이

 

K=1부터 시작해서, 배열에서 1개 지우고 나머지 N-1개에서 최솟값을 찾아 지우고, 평균을 구하고

 

K=2이면, 2개 지우고 나머지 N-2개에서 최솟값을 찾아 지우고, 평균을 구하고.

 

...

 

K=N-2이면, N-2개 지우고 나머지 2개에서 최솟값 찾아 지우고, 평균 구하고

 

이렇게하면, 최솟값 찾는 과정에서 우선순위 큐에 매번 N-1개의 원소넣고 최솟값 찾고

 

N-2개의 원소넣고 최솟값 찾고,

 

N-3개의 원소 넣고 최솟값 찾고,

...

 

이게 매번 반복되니까 도저히 통과를 못하더라

 

그런데 뒤에서부터 시작하면 놀라운 일이 발생한다

 

K = N-2이면, 뒤에서부터 2개에서 최솟값 찾아 빼고, 평균 구하고,

 

K = N-3이면, 수 하나를 우선순위 큐에 넣고 최솟값 찾아 빼고, 평균 구하고,

 

K = N-4이면, 수 하나를 우선순위 큐에 넣고 최솟값 찾아 빼고, 평균 구하고,

 

...

 

K = 1이면, 수 하나를 우선순위 큐에 넣고 최솟값 찾아 빼고, 평균 구하고,

 

..

 

뒤에서부터 시작하면 우선순위 큐 하나에 매 순간 수를 하나씩만 넣어서 최솟값 찾으면 되니 상당히 효율적으로 변한다

 

--------------------------------------------------------------------------------------------------------

 

정리하면 알고리즘이 다음과 같다

 

1) 우선순위 큐에 배열의 마지막 N-1번째 원소를 넣어 초기화

 

2) 우선순위 큐에 들어간 원소의 합을 가지는 total 변수 초기화

 

3) K = N-2부터 K=1까지 4)-7)을 반복

 

4) 우선순위 큐에 수 하나를 넣고, total에 더해준다.

 

5) 최솟값을 찾아 total에 빼준다.

 

6) 평균을 구해 최대 평균을 갱신

 

7) 5)에서 뺀 최솟값을 다시 total에 더해준다

 

import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(arr[n-1]);
        
        int total = arr[n-1];

        double max_mean = 0.0;

        for(int i = n-2; i > 0; i--){

            pq.add(arr[i]);
            total += arr[i];

            int min = pq.peek();

            total -= min;
            
            //정수와 정수끼리 나눗셈은 몫연산
            //실수로 바꿀려면 명시적 형변환을 해줘야함
            if(max_mean < (double)(total/(n-i-1))){
                max_mean = (double)total/(n-i-1);
            }

            total += min;
        }

        System.out.printf("%.2f",max_mean);
    }
}

 

여기서 또 하나의 핵심은... (double)로 바꿔줘야한다는 점이다..

 

이거때문에 왜 틀렸나 또 고민함..

 

정수 total과 정수 n-i-1의 나눗셈은 몫연산을 하게 되므로, 실수 나눗셈을 할려면 앞에 (double)을 반드시 붙여줘야한다...